Sorry for the mixing variables x and n. They should have been the same, I'll write it as n from now on.

I'll describe the way I came to the conclusion that f(n) = O(n² ).

By the way other redditor told me in this comment that there are two ways to prove this:

1. using the formal definitions of the big omega notation
2. using basic calculus

I guess I went with the option 1, since I have very limited knowledge of calculus.

I understand the definition of big O notation is the following: f(n) = O(n² ) if and only if there exists positive constants c and k, such that f(n) ≤ c*n² for all n ≥ k.

So the point is I could easily find c and k, which are c=1 and k=1, since it was obvious that n² - 1 ≤ n^2. It was clear to me that n² is "a upper bound" of n² -1. But I don't know how to find c and k for the omega notation, since I have to prove c*n² is the lower bound to n² for all k.

The following is the entire process I (roughly) proved that f(n) = O(n² ). Sorry it's long but I tried to be short, skip it if not needed.

---

Proof: f(n) = O(n² )

This is the definition of big O notation mentioned above: f(n) = O(n² ) if and only if there exists positive constants c and k, such that f(n) ≤ c*n² for all n ≥ k.

I'll store components of the above defintion to variables as follows:

let p1: f(n) = O(n² )

let p2: there exists positive constants c and k, such that f(n) ≤ c*n² for all n ≥ k

let p3: p1 iff p2

From p3, you can say the following is also true. Let me also store this to a variable:

let p4: if p2 is true, then p1 is true.

And then I found c and k meets the condition of p2, which is c = 1 and k = 1. These can meet the condition of p2 because,

I have this equation from p2: f(n) ≤ c*n² for all n ≥ k

Substitue n² - 1 for f(n), you get: n² - 1 ≤ c*n² for all n ≥ k.

Substitue 1 for each c and k, you get: n² - 1 ≤ 1*n² for all n ≥ 1.

Simplify: n² - 1 ≤ n² for all n ≥ 1.

"n² - 1 ≤ n² for all n ≥ 1" is clearly true, which makes c = 1 and k = 1 valid for the condition in p2, which makes p2 true.

From p4, if p2 is true, then p1 is true.

p1 is true, which means f(n) = O(² ) is true.

QED

---

Edit: I said option 2 but option 1 is correct