0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I've edited my original post since I can't edit comments. $\endgroup$ – mylasthope Nov 8 '14 at 1:43
  • $\begingroup$ It seems that you have some misconceptions about the $\log$ function. I'd suggest reviewing the textbooks/lecture notes before attempting to tackle these problems. In addition, while you can easily claim that $n = O(n^2)$, it is usually more helpful to get tighter bounds, like $n = O(n)$. There exist $\Theta$ bounds for all three questions that you posed. If you find the $\Theta$ bounds, your $O$ bounds will be as tight as possible like the question is requesting. $\endgroup$ – Ashwin Deshpande Nov 8 '14 at 7:13

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.