This question already has an answer here:
- Sorting functions by asymptotic growth 6 answers
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)$.