I tried differentiate the two functions, then I got $\frac{2\log n}{n}$ and $\frac{1}{2\sqrt{n}}$.
Take the limit on the ratio, we can get
$\lim_{n \rightarrow \infty} \frac{2logn/n}{1/2\sqrt{n}} $
Then substitute n by $m^2$,
$\lim_{n \rightarrow \infty} \frac{8logm}{m} = \lim_{n \rightarrow \infty} 8/m = 0$
So $\log^{2}n = O(\sqrt{n})$.
But this is opposite from the plots I got with Matlab. What's wrong here?
As Carl Schildkraut commented, you did not plot the functions over a sufficiently large range.
In the real domain, equation $$\log^2(x)=\sqrt x$$ has three roots expressed in terms of Lambert function $$x_1=e^{-4 W\left(\frac{1}{4}\right)}\approx 0.442394$$ $$x_2=e^{-4 W\left(-\frac{1}{4}\right)}\approx 4.17708$$ $$x_3=e^{-4 W_{-1}\left(-\frac{1}{4}\right)}\approx5503.66$$ which makes $$\log^2(x)\geq\sqrt x \qquad 0\leq x \leq x_1$$ $$\log^2(x)\leq\sqrt x \qquad x_1\leq x \leq x_2$$ $$\log^2(x)\geq\sqrt x \qquad x_2\leq x \leq x_3$$ $$\log^2(x)\leq\sqrt x \qquad x_3\leq x \leq \infty$$
Concerning function $$f(x)=\frac{\log^2(x)}{\sqrt x}$$ its derivatives are$$f'(x)=-\frac{(\log (x)-4) \log (x)}{2 x^{3/2}}$$ $$f''(x)=\frac{\log (x) (3 \log (x)-16)+8}{4 x^{5/2}}$$ The first derivative cancels for $x=1$ and $x=e^4$. The second derivative test shows that the first solution corresponds to a minimum $(f(1)=0,f''(1)=2)$ and that the second solution corresponds to a maximum $(f(e^4)=\frac{16}{e^2},f''(e^4)=-\frac{2}{e^{10}})$
