1
$\begingroup$

Is the first function big oh, theta or omega of the second function in the following examples.

$(\log n)^{\log n} $ and $ \frac{n}{\log n}$
I am not sure how fast the first function grows.

$n2^n$ and $3^n$
I think the second function grows faster but not sure how to prove it.

$(\log n)^{\log n} $ and $2^{(\log_2n)^2}$
This is just puzzling.

$\sum_{i=1 }^n i^k$ and $n^{k+1}$.
And so is this.

Any help is much appreciated.

$\endgroup$
1
$\begingroup$

For the first and the third, taking the logarithm of both sides will really help. For the second, try to use the fact that if $\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0$ then $f(n) = o(g(n))$. For the fourth, try approximating the sum using an integral.

$\endgroup$
  • $\begingroup$ for the first example after taking log of both sides we get $ lognlog(logn) $ and $logn - log(logn) $. Do we say that $log(logn)$ is approximately equal to 1, therefore the two functions are asymptotically equivalent? Thanks for your help $\endgroup$ – matt Apr 10 '17 at 9:58
  • 2
    $\begingroup$ The function $\log\log n$ is definitely not approximately equal to 1. I suggest working it through with a friend or a TA. Also, don't forget that you took the logarithm – even if $\log f = \Theta(\log g)$ it doesn't mean that $f = \Theta(g)$. For example, $\log(2^n) = \Theta(\log(3^n))$. $\endgroup$ – Yuval Filmus Apr 10 '17 at 10:29

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.