I am not sure with this example.
Prove that $n^2$ is $O(1.1^n)$.
Let
- $f(n) = n^2$
- $g(n) = 1.1^n$
In other words, I need to find constant $c$ such that $f(n) = n^2 \leq c\cdot 1.1^n = c \cdot g(n)$.
I start with
$$g(n) = 1.1^n = (1+0.1)^n = \sum_{k=0}^{n} {n \choose k} 1^{n-k}\cdot0.1^k =$$ $$= 1 + 0.1n + 0.01\frac{n(n-1)}{2}+\dots > 1 + 0.1n + 0.01\frac{n(n-1)}{2} = h(n).$$
So, $h(n) < g(n)$. If I show that $f(n)$ is $O(h(n))$, then $f(n)$ is $O(g(n))$
In other words, $f(n) \leq c\cdot h(n) \leq c \cdot g(n)$.
$$h(n) = \frac{1}{2}(2 + 0.19n+0.01n^2)$$
I need find constant $c$ such that
$$n^2 \leq c \cdot \frac{1}{2}(2 + 0.19n+0.01n^2)$$
Let $c = 200$, then
$$n^2 \leq 200 \cdot \frac{1}{2}(2 + 0.19n+0.01n^2) = 200 + 19n + n^2$$ $$0 \leq 200 + 19n$$
This hold for any nonnegative number $n \geq 0$. Since the $g(n) = 1.1^n$ is defined only for nonnegative number $n$, then there is no problem.
Hence $f(n)$ is $O(h(n))$. Therefore $n^2$ is $O(1.1^n)$
I have two questions:
- Is the proof correct?
- Have you a faster method to prove this example?
Thank you.
Every increase of $n$ in $1.1^n$ multiplies it by $1.1$. Meanwhile, $n^2$ is multiplied by $\dfrac{(n+1)^2}{n^2}$, which is smaller as of $n=21$.
$$n\ge21\implies n^2\le \frac{21^2}{1.1^{21}}1.1^n<60\cdot1.1^n.$$