Nachweis der komplizierten wenig - o-Anweisung

Question

Folgende Frage wird als Hausaufgabe gegeben. Egal, wie sehr ich versuchte, es zu lösen, ich war nicht in der Lage, eine Lösung zu finden. Die Frage fragt, ob die gegebene Funktion a ein Element der Menge little-o (b) ist oder nicht.

show that n^(ln(ln(ln(n)))) is o(ceiling(ln(n))!) 

Interessant ist faktorielles Operator ! nicht neben n ist, sondern nur neben ceiling(ln(x)).

Da dies eine kleine-o-Aussage ist, denke ich, dass es mit Limit gelöst werden muss. Ich weiß nicht, was ich für die Platzierung des faktoriellen Operators sagen soll.

Answer 1

Beginnt sie mit dem Logarithmus (Base- n) von beiden Seiten nehmen, die asymptotische Notation als unerfindliche f(n) schreiben:

ln(ln(ln n))) = f(log(n, ceil(ln n)!)) 
       = f(ln(ceil(ln n)!)/ln n) [logarithm rules] 
       = f([ ceil(ln n) ln(ceil(ln n)) - O(ln n) ]/ln n) [Stirling] 
       = f((1 + O(1)) ln(ln n + O(1)) - O(1)) 
       = f(ln(ln n)) 

Wo die zweiten zum letzten Schritt folgt aus der Tatsache, dass die oben abgerundet Der Wert einer Zahl unterscheidet sich immer von ihrem eigenen Wert um weniger als 1 (was offensichtlich eine sehr kleine Größe ist und asymptotisch ignoriert werden kann).

Da ln n = o(n), folgt daraus, dass ln(ln n) = o(ln n) usw. und damit die Blindetikett f(n) = o(n):

n^ln(ln(ln n))) = o(ceil(ln n)!)