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?
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$.