Tilde approximation for $\frac{N^{100}}{2^N}$?
I am having some trouble getting the tilde approximation for a computer algorithms class. Here is what I have so far:
$\frac{N^{100}}{2^N} \rightarrow \lg\left(\frac{N^{100}}{2^N}\right) = \lg(N^{100}) - \lg(2^N) = 100\lg(N) - N\lg(2)$
From here I am stuck. I was thinking that the tilde might be $0$ given that $2^N$ grows faster of the two.
$\endgroup$ 22 Answers
$\begingroup$I don't know if I answered your question:
$f(N) = \frac{N^{100}}{2^N}$ is not only bounded, but it eventually goes to 0, as $N$ goes to infinity. The short answer is that for any positive constants $c$ and $k$ independent of $N$, the function $e^{cN}$ always dominates $N^k$ as $N$ gets large. Even though, depending on the specific values of $c$ and $K$, the value of $N^k$ may be much much larger than $e^{cN}$ for "practical" values of $N$.
ETA: Looks like you already understand this.
So $f(N) \in O(1)$ would technically be correct; $f(N) \in o(1)$ would also be correct (and a stronger statement as $o(1) \subset O(1)$ ). I am really not sure what other answer would be called for here.
What would be incorrect though is $f(N) \in \theta(1)$; that would imply that (put informally) $N^{100}$ and $2^N$ grow roughly proportionally to each other for $N$ arbitrarily large. Put more formally, the statement $f(N) \in \theta(1)$ would imply that there exists an $\epsilon > 0$ such that, for any $N_0$ there is some $N > N_0$ such that $|f(N)| > \epsilon$. And in this particular instance this is not true.
$\endgroup$ $\begingroup$The ratio never exceeds $3.076*10^{172}$ at $N=144$. So I guess the approximation would be a constant.
$\endgroup$ 1
