$ log^*(n) $ Laufzeitanalyse

Question

Ich weiß also, dass $ log^*$ iterierte Logarithmus bedeutet, also $ log^*(3) $ = $ ( log log log log ...) $ bis $ n leq 1 $.

Ich versuche Folgendes zu lösen:

ist

$ log^*(2^{2^n}) $

wenig $ o $, wenig $ Omega $ oder $ theta $ of

$ { log^*(n)}^2 $

In Bezug auf die Innenfunktionen ist $ log^*(2^{2^n}) $ viel größer als $ log^*(n) $, aber das Quadrieren des $ log^*(n) $ wird werfen Ich weg.

Ich weiß, dass $ log (n)^2 $ $ o (n) $ ist, aber ich glaube nicht, dass die Eigenschaft für den iterativen Logarithmus gilt.

Ich habe versucht, die Master -Methode anzuwenden, aber ich habe Probleme mit den Eigenschaften einer Funktion $ log^*(n) $. Ich habe versucht, N auf max zu setzen (dh $ n = 5 $), aber das hat das Problem nicht wirklich vereinfacht.

Hat jemand irgendwelche Tipps, wie ich mich daran nähern sollte?

Answer 1

Erinnern Sie sich daran, dass wir für $ k> 1 $ per Definition $ log^*k = log^*( log {k}) + 1 $ haben.

Indem wir die Definition zweimal anwenden, sehen wir, dass $ log^*(2^{2^n}) = log^*n + 2 $. Jetzt können wir $ log^*n + 2 $ und $ ( log^*n)^2 $ vergleichen.

Answer 2

Lassen Sie es uns herausschreiben und sehen, was wir bekommen. Um die Anzahl der Protokolle zu verfolgen, werde ich sie einschreiben. Ich weiß, das ist normalerweise Basis, wenn jemand eine bessere Idee hat, lass es mich wissen oder bearbeiten:

$$ log^*(2^{2^n}) = log_1 ( log_2 (... log_k (2^{2^n}) ...)) = log_1 .. . log_ {k-1} (2^n log_ {k} (2)) = log_1 ... log_ {k-2} ( log_ {k-1} (2^n)++ log_ {k-1} log_ {k} (2)) = log_1 ... log_ {k-2} (n log_ {k-1} (2)+ log_ {k- 1} log_ {k} (2)) appl log_1 ... log_ {k-2} (n log_ {k-1} (2)) = log_1 ... log_ {k-2} (n+ log_ {k-1} (2)) apper log_1 ... log_ {k-2} (n) $$, da wir nach großem $ suchen n $, ich habe die additiven Begriffe $ log ( log (2)) ca. 0,3665 $ und $ log (2) ca.0,693 $ fallen gelassen.

Dies zeigt, dass $ log^*(2^{2^n}) = k $, $ log^*(n) ca. k-2 $ oder kombiniert, $$ log^*(2^ {2^n}) ca. log^*(n) +2 $$

Die großen-$ theta $ s sind identisch, und wie in den Kommentaren ausgeführt wird, sind die Gleichungen identisch gleich.