Cormen Edition 3 Exercise 3.1 Question 2 (Page No. 52)

Question

Show that for any real constants $a$ and $b$, where $b > 0,$
$(n+a)^b=\Theta(n^b)$

Answer 1

According to binomial theorem,

$\large (n+a)^b = \binom{b}{0}n^b a^0 + \binom{b}{1}n^{b-1} a^1 + \binom{b}{2}n^{b-2} a^2 + ...... + \binom{b}{b}n^{0} a^b$

term with largest power of n after expansion is $\large \binom{b}{0}n^b a^0 = n^b$ and for calculating $\Theta$ we can ignore other terms with less power of n.

Hence,

$(n+a)^b=\Theta(n^b)$