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
    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$ 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, privacy policy and cookie policy

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