2

I have to prove or disprove the following statement:

$\forall a,b \in \mathbb{R}$, $b > 1$ : $n^a \in O(b^n)$

Clearly there are 2 cases:

(i) $a < 0$ and (ii) $a \geq 0$,

meaning that I have to prove:

(i) $\frac{1}{n^a} \leq c \cdot b^n$

(ii) $ n^a \leq c \cdot b^n$

and this is where I already get stuck..

Do you guys have any idea?

tenacious
  • 23

1 Answers1

0

In any case,

$$\frac{n^a}{b^n}\rightarrow 0$$

So

$$n^a=o(b^n)$$

So also

$$n^a=O(b^n)$$

You can prove the limit this way:

Let

$$u_n=\frac{n^a}{b^n}$$

Then

$$\frac{u_{n+1}}{u_n}=\frac{(n+1)^ab^{n}}{n^ab^{n+1}}=\frac1b\left(1+\frac 1n\right)^a$$

Since $1+\frac1n\rightarrow 1$ and $b>1$, there is an $N$ and $\epsilon$ such that the quotient $\frac{u_{n+1}}{u_n}<\epsilon<1$ for all $n>N$, so $u_n<A\epsilon^n \rightarrow 0$.

Jean-Claude Arbaut
  • 23,277
  • But doesn't n^a / b^n --> 0 mean that n^a is not in O(b^n)? Because I found the following definiton in my script: lim n -> a f(n)/g(n) = A ≠ 0 where A is a constant <=> f(n) is in O(g(n)) – tenacious May 12 '14 at 15:45
  • @user149560 No, my definition is $f(n)=O(g(n))$ iff there is a $C$ such that $f(x) \leq C g(x)$. See here, here and there. If $f(n)/g(n) \rightarrow 1$, you would write $f(n) \sim g(n)$. If you got a different notation in classroom, use it of course, and adapt the notation (the proof is the same, since only the notation would change) – Jean-Claude Arbaut May 12 '14 at 16:07