Big Oh Notation Proof [closed]

Question

The question is to prove that

• f(n) = 4n⁵ - 17n⁴ - 33n³ - 13n²

is in Θ(n⁵)

What I tried to do what split up 4n⁵ into two separate constants (2n⁵ + 2n⁵) and make that whole equation greater than or equal to 2n⁵ and got C = 2, N >= 6.

I'm unsure if I'm right and I'm still quite unsure how to actually prove that function is in Θ(n⁵). I hope someone can come along and help me solve this and what steps to take in order to prove other Big Oh notation problems.

Thank you for the help guys!

Answer 1

f(n) ∈ Θ(g(n)) (more general):

We have to show that there exists positive M and N such that

g(n) * M <= f(n) <= g(n) * N

for large enough ns. In this case, that's

M * n5 &lt= 4n5 - 17n4 - 33n3 - 13n2 &lt= N * n5

Divide by n5:

M &lt= 4 - 17(1/n) - 33(1/n2) - 13(1/n3) &lt= N

For large ns, we'll be left with

M &lt= 4 - ε &lt= N

We can pick M = 3 and N = 4.

---

f(n) ∈ O(g(n)) (more specific):

This actually follows from the result above, but we can provide a specific proof as well.

We have to show that there exists a positive N such that

|f(n)| <= g(n) * N

for large enough ns. In this case, that's

|4n5 - 17n4 - 33n3 - 13n2| &lt= N * n5

Divide by n5:

4 - 17(1/n) - 33(1/n2) - 13(1/n3) &lt= N

For large ns, we'll be left with

4 - ε &lt= N

We can pick N = 4.

---

Reference:

• Family of Bachmann–Landau notations