Comparing asymptotic running time of two algorithms $\sqrt n$ and $2^{\sqrt{\log _{2}n}}$

Question

Given two algorithms with their time-complexity $t_a(n)=\sqrt{n}$ and $t_b(n) = 2^{\sqrt{\log _{2}n}}$ and i have to show $t_b(n) = O(t_a(n)) $.

I´ve made a program to check this statement and it seems that for any given $c>0,\forall n\geq16$ it holds, however i don´t know how to formally proof this ,because i can´t find any simplification for $t_b$.

I know that i must prove $ \exists c : \forall n \geq N:t_b(n) \leq c *t_a(n)$ using big-O-Notation.

A hint/solution-idea would be really great.

Answer 1

In order to compare two quantities/expression, it is often easier if they are in the same form. Here try expressing $t_a(n)$ as $2^{s_a(n)}$ and compare $s_a(n)$ with $\sqrt{\log_2 n}$.

Additionally, beware of using a program to check asymptotic comparisons: e.g. $f(n)=n^{10^6}$ and $g(n)=(1,0000000000000001)^n$

Answer 2

We can simplify $t_b(n): $ $$t_b(n) =2^{\sqrt{\log _{2}n}}$$ $$=\left(2^{\log _{2}n}\right)^{\frac{1}{\sqrt{\log _{2}n}}} $$ $$=\left(n^{\log _{2}2}\right)^{\frac{1}{\sqrt{\log _{2}n}}} $$ $$=n^{{\frac{1}{\sqrt{\log _{2}n}}}}$$ $$=\sqrt[\sqrt{\log_2 n}]{n}.$$

Therefore $$\left(\sqrt[\sqrt{\log_2 n}]{n}\right)=\mathcal{O}\left(\sqrt{n}\right)$$ because $$\lim_{n\to\infty}\frac{\left(\sqrt[\sqrt{\log_2 n}]{n}\right)}{\left(\sqrt{n}\right)}=0.$$