algorithm question how prove that $(n+a)^b = \Theta(n^b)$

Question

this question doctor in college give us as home work

but I don't know how approve it

Answer 1

Recall that $f \in \Theta(g)$ whenever $k_1g(x) \leq f(x)$ an $f(x) \leq k_2g(x)$ for some constants $k_1$, $k_2$ and all $x$ greater than or equal to some $N$. In this case, you must show that there are constants $k_1$ and $k_2$ such that $k_1n^b \leq (n + a)^b$ and $(n + a)^b \leq k_2n^b$ for all $n$ greater than or equal to some $N$. If we choose $k_1$ so that $k_1^{1/b} \leq 1 + a/n$ for all $n \geq N_1$, then we obtain $k_1n^b \leq (n + a)^b$. Similarly, if we choose $k_2$ so that $1 + a/n \leq k_2^{1/b}$ for all $n \geq N_2$, then we obtain $(n + a)^b \leq k^2n^b$. Is it always possible to choose such $k_1$ and $k_2$? Recall what happens to $a/n$ as $n$ becomes arbitrarily large.

Answer 2

Write

$${(n+a)^b \over n^b} = \left(1+{a\over n}\right)^b$$

Then let $n \to \infty$ and conclude!

And of course, see here if you don't know the big theta notation. It's more or less the same as big O (that is, upper bound) with additional lower bound of the same order.

Answer 3

For every $n\geqslant2|a|$, one has $\left(\frac12\right)^b\cdot n^b\leqslant(n+a)^b\leqslant\left(\frac32\right)^b\cdot n^b$.