Search code examples
mathbig-ologarithmclrslittle-o

CLRS exercise 3.2-4 Big-Oh vs Little Oh

I'm self studying CLRS, and I've hit this point - the question I'm answering is:

Is the function ⌈lglgn⌉! polynomially bounded?

And I've reduced it down to 

=Θ(lglgn⋅lglglgn)

Now, all the solutions manuals seem to use little oh at this point to get it down to

=o(lglgn⋅lglgn)

And this step confounds me a little; I thought I understood little-oh, but clearly not well enough - can somebody frame it within this particular context? Also the next steps go from 

=o(lg^2 n)

to

=o(lgn)

is this merely an application of L'hopitals rule?

Solution

  • If you have a function that is asymptotically equivalent to lglgn⋅lglglgn (so it is in Θ(lglgn⋅lglglgn)), then lglgn⋅lglgn is an upper bound since lglglgn is in o(lglgn).

    I'm not sure about the last step:

    • If o(lg^2 n) means o((lg n)^2), you cannot say it is in o(lg n). This is just wrong.
    • If o(lg^2 n) means o(lglg n), this is just switching to a larger upper bound due to lglg n is in o(ln n).