C03 - Problem 2

[swethmandava]

a )
for 0 < epsilon < 1,

lg^k n > n^epsilon

and for epsilon >= 1,

lg^k n) < n^epsilon

Therefore, the correct answer is
YES YES YES YES YES

[gzc]

Thanks, I will specially mark it in my solution

[hsingchien]

It does not matter what epsilon is. Use L'Hôpital's rule recursively for k times to calculate the lim(n→∞){lg(n)^k/n^ε}, you'll finally get k!/(ε^k*n^ε), which is 0 as both k and ε are constant. Therefore the answer should be only o and O are yes. You can also easily verify this by plotting in matlab. The difference is quite obvious.

[kestory]

the correct answer for (a) is
YES YES YES YES NO

[jotarios]

the correct answer for (a) is
YES YES YES YES NO

If there exist any two functions f(n) and g(n), and we have f(n) = \Theta(g(n)) if only and if f(n) = O(g(n)) and f(n) = \BigOmega(g(n)). You can check Theorem 3.1 in the book.

Thus, if you say YES and YES for O and \BigOmega, then is YES for \Theta. So, you answer should be YES YES YES YES YES.

---

BTW, I think the correct answer is YES YES NO NO NO.