Question

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

Answer 1

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)`