Tilde approximation for $\frac{N^{100}}{2^N}$?

3.8k Views Asked by At

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.

1

There are 1 best solutions below

1
On

The ratio never exceeds $3.076*10^{172}$ at $N=144$. So I guess the approximation would be a constant.