Question

Show that 20n + 12 n²-5 is e(n). (That is show that it is theta of n raised to the power 5).

Answer 1

The Θ notation in time complexity is defined as :

f(n) = Θ(g(n)) if there exists 3 positive constants c1,c2 and n0 such that 0 <= c1*g(n) <= f(n) < c2*g(n) for every n >= n0.

The given function f(n) = 20n^5 + 12n^2 - 5

g(n) = n^5

Then, according to the Θ notation :

c1*(n^5) <= 20n^5 + 12n^2 - 5 <= c2*(n^5)

Solving the left side inequality, we get :

c1*(n^5) <= 20n^5 + 12n^2 - 5

Divide both sides by n^5,

c1 <= 20 + ( 12 / n^3 ) - ( 5 / n^5 )

As the value of n tends to ∞, the terms ( 12 / n^3 ) and ( 5 / n^5 ) become 0.

So, for large values of n,

c1 <= 20.

Solving the right side inequality, we get :

c2*(n^5) >= 20n^5 + 12n^2 - 5

Divide both sides by n^5,

c2 >= 20 + ( 12 / n^3 ) - ( 5 / n^5 )

As the value of n tends to ∞, the terms ( 12 / n^3 ) and ( 5 / n^5 ) become 0.

So, for large values of n,

c2 >= 20.

Thus, there exist positive values of c1 and c2.

Therefore, the Θ notation definition is satisfied.

So, it is proved that 20n^5 + 12n^2 - 5 is Θ( n^5 ).