How to solve a problem on relative asymptotic growth (table) from CLRS?

Question

I struggle to fill this table in even though I took calculus recently and good at math. It is only specified in the chapter how to deal with lim(n^k/c^n), but I have no idea how to compare other functions. I checked the solution manual and no info on that, only a table with answers which provides little insight.

Answer 1

When I solve these I don't really think about limits -- I lean on a couple facts and some well-known properties of big-O notation.

Fact 1: for all functions f and g and all exponents p > 0, we have f(n) = O(g(n)) if and only if f(n)^p = O(g(n)^p), and likewise with o, Ω, ω, and Θ respectively. This has a straightforward proof from the definition; you just have to raise the constant c to the power p as well.

Fact 2: for all exponents ε > 0, the function lg(n) is o(n^ε). This follows from l'Hôpital's rule for limits: lim lg(n)/n^ε = lim (lg(e)/n)/(ε n^ε−1) = (lg(e)/ε) lim n^−ε = 0.

Fact 3:

• If f(n) ≤ g(n) + O(1), then 2^f(n) = O(2^g(n)).
• If f(n) ≤ g(n) − ω(1), then 2^f(n) = o(2^g(n)).
• If f(n) ≥ g(n) − O(1), then 2^f(n) = Ω(2^g(n)).
• If f(n) ≥ g(n) + ω(1), then 2^f(n) = ω(2^g(n)).

Fact 4: lg(n!) = Θ(n lg(n)). The proof uses Stirling's approximation.

To solve (a), use Fact 1 to raise both sides to the power of 1/k and apply Fact 2.

To solve (b), rewrite n^k = 2^lg(n)k and cⁿ = 2^lg(c)n, prove that lg(c) n − lg(n) k = ω(1), and apply Fact 3.

(c) is special. n^sin(n) ends up anywhere between 0 and n. Since 0 is o(√n) and n is ω(√n), that's a solid row of NO.

To solve (d), observe that n ≥ n/2 + ω(1) and apply Fact 3.

To solve (e), rewrite n^lg(c) = 2^lg(n)lg(c) = 2^lg(c)lg(n) = c^lg(n).

To solve (f), use Fact 4 and find that lg(n!) = Θ(n lg(n)) = lg(nⁿ).