$g(n)$ upperbounds $f(n)$ but graph shows otherwise

Question

Given we have the following functions:

$$f(n)=\log_{2}^{4}n$$ $$g(n)=2^{\sqrt{\log_{2}n}}$$

I've done the limit of f(n) over g(n), and found that g(n) is an upperbound of f(n) given the zero result:

$$\lim_{n \to \infty} \frac{\log_{2}^{4}n}{2^{\sqrt{\log_{2}n}}}=0$$

This means that at a sufficiently large n, g(n) should be greater than f(n), but when I graph them together, no matter how big I set n, I cannot see a trend of g(n) eventually overcoming f(n).

Could this be because the value of n needs to be unimaginably large, that I cannot see it on a graph? If this is the case, is there still merit in stating that g(n) is the upperbound of f(n)?

Answer 1

Pick $n = 2^K$ for some large $K$. Then \begin{align} f(n) &= [\log_2(n)]^4 \\ &= K^4\\ &= {2^{\log_2(K)}}^4 \\ &= 2^{4\log_2(K)} \\ \end{align} while \begin{align} g(n) &= 2^\sqrt{\log_2 N} \\ &= 2^\sqrt{K} \end{align}

So when $\sqrt{K}$ is larger than $4 \log_2{K}$, $g$ will be larger than $f$. Let's try $K = 100$: $$ \sqrt{100} = 10\\ 4 \log_2{100} \approx 4 \cdot 6.65 \approx 26 $$

Nope. Not quite big enough. The actual crossover seems to happen at about $K = 1900$, so let's try $K = 2000$. In that case we have $$ \sqrt{2000} \approx 44.72...\\ 4 \log_2{2000} \approx 43.86... $$

How large is $N = 2^{2000}$? Well, $10 \approx 2^{3.32}$, so $N$ is about $$ 10^{\frac{2000}{3.32}} \approx 10^{602} $$ i.e., a 602-digit number. So I guess your conjecture about "because the value of $n$ needs to be unimaginably large, that I cannot see it on a graph?" is a reasonable one.

I like to keep in mind that there are something like $10^{51}$ elementary particles in the universe, so that if you are working on some algorithm, it's hard to imagine a practical instance in which $n$ is larger than this. On the other hand, if you're doing mathematical analysis and studying asymptotic behavior, numbers like this are perfectly reasonable.

Also, to backpedal a little bit on that $10^{51}$ thing

• you might have more than that many moments to consider in some algorithm that considers time-varying data

• knowing an upper bound for something can help the next person developing an algorithm know a little bit more about where to look, so even wild things like this can be useful

Answer 2

If you let $n=2^{x^2}$, then $f=x^8$ and $g=2^x$.

$$x^8=2^x \qquad \implies \qquad 8\log(x)=x \log(2)$$ which is much easier to visualize.

The exact solution is given in terms of Lambert function $$x=-\frac{8 }{\log (2)}\,\,W_{-1}\left(-\frac{\log (2)}{8}\right)$$ which, numerically, is $43.5593$.

So, $n=1.5034\times 10^{571}$