Could not understand 3.2.4

[SachinBahukhandi]

Hi there, Thank you for helping us out. I do not have an issue but need help on understanding this: =Θ(lg n lg lg n) =ω(lg n) ​How did you express this in the form of omega. Did you use the identity: =ω(2^n)? Thank you.

[qstratton]

Hello,

Here is a different way of viewing the problem assuming you accept that lg(ceil(lg n)!) = Θ(lg n lg lg n). Let f(n) = lg(ceil(lg n)!). By definition, this means that there exist positive constants n_0 and c_0 such that 0 <= c_0 lg n lg lg n <= f(n) for all n >= n_0. Suppose for the sake of contradiction that f(n) = O(lg n). Then there would exist positive constants n_1 and c_1 such that f(n) <= c_1 lg n for all n >= n_1. Now suppose n > max(n_0, n_1, 1). Then, c_0 lg n lg lg n <= f(n) <= c_1 lg n which since n > 1 implies that lg lg n <= c, where c = c_1/c_0. Hence, lg lg n is bounded above by a constant for arbitrarily large n which is a contradiction, so f(n) is not O(lg n).