I did not understand few results from the book problem.
Here is the problem:
Indicate, for each pair of expressions (A, B) in the table below, whether A is
O, o, Ω, ω, Θ of B. Assume that k ≥ 1, > 0, and c > 1 are constants.
And solution:
I am not sure
- why c. has all NO. How is this can even be the case?
- why e. has YES for Ω and Θ . Asymptotically $c^{lg(n)}$ grow faster than $n^{lg(c)}$, right? Why $n^{lg(c)}$ is not in o($c^{lg(n)}$) ?
- why f. has YES for Ω and Θ . It also seems that asymptotacally $lg(n^n)$ grows faster than $lg(n!)$ . Why $lg(n!)$ is not in o($lg(n^n)$) ?
For c: due to $\sin n$ this function is unbounded, so there doesn't exist $c$ such that any of the order functions hold
For e: consider taking $n = e^t$
For f: use Stirling's formula or Euler-Maclaurin for $\sum_k \log k$, these functions are of the same order.