3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much! $\endgroup$ – BMAY Jan 14 at 16:40
  • $\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$ – Hermann Gruber Jan 15 at 7:02

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.