1

H. Cormen, Exercise 3.1-2

The following statement is true? If yes, prove that it is true.

$$ (n+a)^b = Θ(n^b)\\ a, b \in R\\ b>0 $$


I tried to expand $(n+a)^b$ using the Binomial theorem, but I couldn't solve this.

Any help?

Semiclassical
  • 15,842
richardaum
  • 279
  • 1
  • 3
  • 12

2 Answers2

1

Notice that $$\lim_{n\to +\infty}\frac{(n+a)^b}{n^b}=1,$$ hence there is some $n_0$ for which if $n\geqslant n_0$, $$\frac 12 n^b\leqslant (n+a)^b\leqslant \frac 32 n^b.$$ This proves that for some $M$, the inequality $$\frac 1M\leqslant \frac{(n+a)^b}{n^b}\leqslant M$$ holds for each $n\geqslant 1$.

More generally, if $(a_n)_{n\geqslant 1}$ and $(b_n)_{n\geqslant 1}$ are two sequences of positive numbers such that $(a_n/b_n)_{n\geqslant 1}$ converges to a positive number, then $a_n=\Theta(b_n)$.

Davide Giraudo
  • 172,925
0

for $n>a \ (n+a)^b = (n(1+\frac{a}{n}))^b = O(n^b) \cdot O(1)$. From this you can easily deduce the lower bound.

Alex
  • 19,262
  • Is it right: $n>a(n+a)^b$ ? – richardaum Jun 26 '14 at 20:28
  • I'm not quite sure what you mean, but using Bernoulli's inequality it'easy to see for example that $(1+\frac{a}{n})^b >1+\frac{ab}{n} = O(1)$ – Alex Jun 26 '14 at 20:30
  • You said: $n>a(n+a)^b$ but there isn't $a$ that mutiplies $(n+a)^b$. This statement is wrong, I guess. Even so, $n>(n+a)^b$ <= This is not true. – richardaum Jun 26 '14 at 20:35
  • oh no what I meant is that for $n>a$ the following statement holds. It's just a blank space between $a$ and the bracket) – Alex Jun 26 '14 at 20:37
  • There is a step between $n^b(1+a/n)^b$ and $O(n^b).O(1)$ that's not so intuitive. Where $O(1)$ came out? – richardaum Jun 26 '14 at 21:06
  • 1
    If $a$ is a positive constant then $(1+\frac{a}{n})>1 = \Omega(1)$ and you can pick a constant larger than 1 s.t. $1+\frac{a}{n} = O(1)$. The same logic applies if $a$ is negative. $O(1)$ means a constant. – Alex Jun 26 '14 at 21:50