Thetha notation proving of function

Question

f(n) = 4n² + 3n - 5 = Theta(n²)

How can I prove this? According to my research , this notation should be like;

for positive constants c1, c2 and n0 such that c1 * g(n) <= f(n) <= c2 * g(n) for all n >= n0 but I couldn't do.

Answer 1

We have f(n) = 4n² + 3n - 5.

---

Claim 1: f(n) <= 5n² for all n

We have 5n² - f(n) = n² - 3n + 5 = (n - 3/2)² + (11/4) > 0 for all n.

Claim 2: 4n² <= f(n) for n >= 2

We have f(n) - 4n² = 3n - 5 >= 0 for n >= 5/3 >= 2.

---

From the above we have 4n² <= f(n) <= 5n² for n >= 2.

Compare with the big theta definition c1 * g(n) <= f(n) <= c2 * g(n) for all n >= n0.

We have c1 = 4, c2 = 5, g(n) = n², and, n0 = 2.

Answer 2

First step, let's fill in the equation and see what we would need to prove.

c1 * n² <= 4n² + 3n - 5 <= c2 * n² (for n >= n0)

I will prove half of it, and leave the remainder to you.

Assume

c1 = 3 (since it makes sense that 3n² <= 4n² for n >= n0)

We need to prove that

3n² <= 4n² + 3n - 5

This is equivalent to proving

4n² + 3n  - 5 - 3n² >= 0 (for n >= n0)
n² + 3n - 5 >= 0

We know this function is a parabola, and we know the sign of the dominant term (n²) is positive. So it must be a valley-shaped parabola.

To find a suitable value for n0, we can look at the roots of the parabola. They are -1.844 and 0.844 (rounded). So assuming n0 = 2 would suffice. In short:

n0 >= 2  
c1 = 3  
c2 = 5  

If you apply the same reasoning for the other half of the proof, you will get another bound for n0. Then, all you need to do is consolidate both bounds.

Answer 3

4n² will grow faster than 3n² and slower than 5n². Remains to find as of which n value the inequalities hold.

From a plot, n0=2 will work.

You can show this more formally, but parabolas cannot lie.