I have been given this problem and I have to decide whether it it true or false.
$$ (\log_2 n)^{\sqrt{ \log_2 n}} = \mathcal{O}(n^{50}) $$
This is my solution. Let
$$ \text{Let } f(n)= (\log_2 n)^{\sqrt{ \log_2 n}} \text{ and } g(n)=n^{50} \\ $$ Now define two new functions.
$$ \text{Let } f^{*}(n):= \log {f(n)} \text{ and } g^{*}(n):= \log {g(n)} \\ $$
So,
$$ f^{*}(n):= \log {f(n)} = (\log_2({\log_2 n}))\sqrt{\log_2 {n}} = \mathcal{O}((\log n)^{3/2}) \\ g^{*}(n):= \log {g(n)} = 50\log_2n = \mathcal{O}(\log n) \\ $$ Now if we examine the asymptotic behaviour of these two functions we find that $$ f^{*} = \Omega(g^{*}) $$ Thus we can conclude that $f = \Omega(g)$. Hence, the statement is false.
Is my solution correct? I feel intuitively that $n^{50}$ is much bigger than $(\log_2 n)^{\sqrt{ \log_2 n}}$
It is true that $(\log_2(\log_2 n))\sqrt {\log_2 n}=O((\log_2 n)^{3/2})$ but this is not useful.
For all sufficiently large $m$ we have $\log_2 m=3\cdot\log_2 (m^{1/3})<3\cdot\frac { m^{1/3}}{3}=m^{1/3}.$ So with $m=\log_2 n$ we have $\log_2(\log_2 n)<(\log_2 n)^{1/3}$ for all sufficiently large $n.$
So $f^*(n)=O(\,(\log_2 n)^{1/3}\sqrt {\log_2 n}\;)=O(\,(\log_2 n)^{5/6}).$
So $f^*(n)/g^*(n)\to 0.$
The Landau big-O gives a "ceiling" on the kind of growth. In this Q we want a much lower ceiling on $f^*(n)$ than $(\log_2 n)^{3/2}.$
In general, if $r,s>0$ and $B>1$ then $\lim_{x\to\infty}\dfrac {(\log_B x)^r}{x^s}=0.$