CLRS осуществлять 3.2-4 Big-Oh против Маленького Oh

Question

Я самостоятельно изучать КСПС, и я ударил эту точку - вопрос Я отвечаю на это:

Is the function ⌈lglgn⌉! polynomially bounded? 

И я свел его вплоть до

=Θ(lglgn⋅lglglgn) 

Теперь все решения руководства, кажется, используют немного о в этой точке, чтобы получить его до

=o(lglgn⋅lglgn)

И этот шаг меня немного смущает; Я думал, что мало что понимаю, ох, но явно недостаточно. Может ли кто-нибудь создать его в этом конкретном контексте? Кроме того, следующие шаги идут от

=o(lg^2 n) 

в

=o(lgn) 

это просто применение L'hopitals правила?

Answer 1

Если у вас есть функция, которая асимптотически эквивалентна lglgn⋅lglglgn (так что в Θ(lglgn⋅lglglgn)), то lglgn⋅lglgn является верхней границей, так как lglglgn в o(lglgn).

Я не уверен, что на последнем этапе:

• Если o(lg^2 n) означает o((lg n)^2), вы не можете сказать, что это в o(lg n). Это просто неправильно.
• Если o(lg^2 n) означает o(lglg n), это просто переход на более крупную верхнюю границу из-за lglg n в o(ln n).