52.5k views
5 votes
. Prove that every polynomial of degree k, p(n) = aknk + ak-1nk-1 + ... +a0 with ak> 0, belongs to \Theta (nk)

1 Answer

2 votes

Answer:

The answer is explained below

Step-by-step explanation:

i)
p(n) \ is\ an\ element\ of\ O(n^k)

Therefore
p(n)\leq c.n^k,therefore\ p(n) \ is\ an\ element\ of\ O(n^k)

ii)
p(n) \ is\ an\ element\ of\ \Omega(n^k)


p(n)=a_kn^k+a_(k-1)n^(k-1)+.\ .\ .+a_o\\p(n)=a_kn^k(1+(a_(k-1))/(a_k)(1)/(n) +.\ .\ .+(a_o)/(a_k)(1)/(n_k) )\\p(n)=1, as\ n\ tends\ to\ \infty, the \ limit\ in\ the \ parenthesis=1. For\ c=(1)/(2)a_k,n\geq n_o \\Therefore:\\p(n)\ge (1)/(2)a_kn^k=c.n^k


p(n) \ is\ an\ element\ of\ \Omega(n^k)

From i and ii,
p(n) \ is\ an\ element\ of\ \Theta(n^k)

User Canen
by
7.5k points