So I'm given the following big-oh hierarchy (each sequence is big-oh of any seqeuence to its right.)
$1$, $\log_2{n}$, ... , $\sqrt[4]{n}$, $\sqrt[3]{n}$, $\sqrt{n}$, $n\log_2{n}$, $n\sqrt{n}$, $n^2$, ... $n^n$.
I need to prove the following:
1) $n + 3\log_2{n}$ $= O(a(n))$ and $a(n)$ is as far left as possible in the hierarchy.
2) $(n*log_2{(n+1))^2} = O(a(n))$ and $a(n)$ is as far left as possible in the hierarchy.
3) $(n + 1)! = O(a(n))$ and $a(n)$ is as far left as possible in the hierarchy.
I've never dealt with logs or factorials, so I'm not quite sure where to begin.
I'm looking over the only example dealing with logs in the book, and it shows that
log base 2 of $n^m$ = $m * $log base 2 of $n$ < $2m * \sqrt{n}$.
In general, is that how I go about converting from log base 2 to a square root--by moving the 2 to the front and multiplying it with the square root of n? Or does this only hold because of of the inequality sign?
For 1)
Need to show: $n + 3\log_2{n} \le C * n\log_2{n}$
$n + 3\log_2{n} \le 3n\log_2{1} + 3log_2{n}$
$n + 3\log_2{n} \le 9n\log_2{n}$
for 2)
I chose $n^2$ as $a(n)$. If this does not work, please let me know.
show: $(n * log_2{(n+1)})^2 \le C * n^2$
I'm not sure what to do with the $(log_2{(n+1)})^2$ however. I'm trying to look up what to do when squaring a logarithm, but I'm not finding a definite answer.
1) Which term dominates as $n$ grows large, $n$ or $3(\log_2{n})$?
2) Think about the identity: $(ab)^c = a^cb^c$
3) Use Stirling's approximation - $n! \approx (\frac{n}{e})^n \sqrt{2\pi n}$
As for your comment, you cannot convert between $\log{n}$ and $\sqrt{n}$. $\log$ is the inverse function of exponentiation, so $e^{\log{g(n)}} = g(n)$. Roots on the other hand are inverse functions of powers, so $\sqrt[k]{g(n)^k} = g(n)$. Your statement is true for large n because $\sqrt{n}$ grows faster than $\log_2{n}$. (Adding in a coefficient of 2 doesn't hurt either).
Try plotting $f(n)=\frac{a*\log{n}}{\sqrt{n}}$. No matter what constant $a$ you choose, $f(n)$ will go to $0$ for large $n$. This indicates that $\sqrt{n}$ grows asymptotically faster than $\log{n}$.