Polynomials and logarithms

Exercise 1.7

Prove the following asymptotic identities.

• For every polynomial p(n) = a_kn^k + a_{k-1}n^{k-1} + \dots + a_1n + a_0 with a_k > 0, it holds that p(n)=\Theta(n^k).
  
  
  
  
  
  
  
  
  

• For every two bases a,b > 1, it holds that \log_a n=\Theta(\log_b n).