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.


2 Answers 2


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$

  • $\begingroup$ Thank you very much! $\endgroup$
    – BMAY
    Commented Jan 14, 2020 at 16:40
  • 1
    $\begingroup$ Really an instructive answer! Btw I recently stumbled across $t_b(n)$ in some research work, when I was looking for a function $f$ with $f(n)^{\log f(n)}=O(n)$. I applied this trick to get an intuition. $\endgroup$ Commented Jan 15, 2020 at 7:02

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.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.