I was wondering if you could double check on the following statements being true, false or non-conclusive (as in in some cases true, but false in others). Here they are:

1) $F(n) = \log (n^n)$ implies $F(n) = \Theta(\log n)$.

Answer: It is a tough one? It is confusing because of $n^n$. My assumption would be to have it as non-conclusive. It is because for some cases, where $n$ is even a bit large, $\log$ will greatly decrease $F(n)$'s value. For abysmally large numbers, it will be significant, i.e. $n = 10000000$. Maybe I am wrong?

2) $F(n) = n \log n + n^2$ implies $F(n) = \Omega(n \log n)$.

Answer: True. We drop $n \log n$ (since it is not significant) and indeed $n^2$ will grow asymptotically faster (it is slower) than $n \log n$.

3) $F(n) = n!$ implies that $F(n) = O(2^n)$.

Answer: False. $n!$ grows faster than $2^n$. Therefore it would be $\Omega(2^n)$ not $O(2^n)$.

  • 2
    $\begingroup$ We don't usually check answers to exercises. $\endgroup$ – Yuval Filmus Sep 19 '16 at 19:08
  • 1
    $\begingroup$ This question appears to be unsuited for this site because questions of the form: "This is the exercise problem, this is my solution. Please grade!" are not interesting for anyone but you. Please see this related meta discussion, and these hints on asking questions about exercise problems. If you want to ask a specific question about a specific part of your attempt, please edit the question accordingly and it may be reopened. Otherwise, you might want to visit Computer Science Chat and get some feedback there. $\endgroup$ – Raphael Sep 19 '16 at 19:45
  • $\begingroup$ That said, you don't give any proof, only claims. $\endgroup$ – Raphael Sep 19 '16 at 19:46
  • $\begingroup$ For (1), $\log(n^n)=n\log(n)$ $\endgroup$ – Rick Decker Sep 20 '16 at 1:34

The function $\log(n^n) = n\log n$ grows much faster than $\log n$, so we can conclusively say that $\log(n^n) = \omega(\log n)$. It even grows much faster than $n$, so $\log(n^n) = \omega(n)$.

You say that whether $\log(n^n) = \Theta(\log n)$ (where perhaps you mean $\Theta(n)$ instead of $\Theta(\log n)$) is "inconclusive", since for small $n$ there is one behavior, and for large $n$ there is another. For asymptotic analysis we care only about the behavior for large $n$.

  • $\begingroup$ Thank you for your explanation. The other 2 are correct right? $\endgroup$ – Cesar A Sep 19 '16 at 19:37
  • $\begingroup$ That's for your TA to say. $\endgroup$ – Yuval Filmus Sep 19 '16 at 21:39

Not the answer you're looking for? Browse other questions tagged or ask your own question.