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

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

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

• Thank you very much!
– BMAY
Jan 14, 2020 at 16:40
• 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. 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.$$