0

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: enter image description here

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)$) ?
UserMoon
  • 349

1 Answers1

1

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.

Alex
  • 19,262
  • I still do not understand c part. Why is this function not exponential? – UserMoon Jan 27 '15 at 00:59
  • $n^{\sin n}$ is unbounded, i.e. it can take very small (e.g. $\frac{1}{1000}$) and very large (e.g. 1000) values infintely often due to $\sin n$ periodicity. Hence we can't find a constant for which the asymptotic ratio will hold – Alex Jan 27 '15 at 09:31