Wann ist die Basis von log für die Komplexitätsklasse egal?

Question

Aufgabe:

Unter welchen Umständen hat die Basis der Logarithmus keinen Einfluss auf die Einordnung in die Komplexitätsklasse

Problem/Ansatz:

Man lernt ja dass die Basis des Logarithmus prinzipiell egal ist. Aber irgendwie ja auch nicht.

Zb ist 4^(log4(n)) in theta von n und 4^(log2(n)) in der Komplexitätsklasse von n^2 (leicht umformbar mit Logarithmus Regeln) und das ist ein fundamentaler Unterschied. Kann mir jemand erklären wann man diese Regel anzuwenden ist bzw wie man das erkennt? Steh da irgendwie auf dem Schlauch.

Answer 1

Ich meine, es gilt folgendes:

Ist \(\Lambda\) irgendein Landau-Symbol,

dann gilt für Funktionen \(f,g\)  und Konstanten \(a\neq 0\):

\(f\in \Lambda(g)\iff f\in \Lambda(a\cdot g)\) und

\(f\in \Lambda(g)\iff a\cdot f\in \Lambda(g)\)

Gemäß hallo97 spielt dann die Basis des Logarithmus

keine Rolle.

Answer 2

Hallo :-)

Man kann jeden Logarithmus (zur beliebigen Basis) mithilfe des natürlichen Logarithmuses umschreiben:

$$ \log_b(x)=\frac{\ln(x)}{\ln(b)}, \quad b>1 $$

Dabei ist \(\ln(b)\) auch nur eine Konstante. Aufgrund dieser Tatsache ist man faul und man lässt das b beim Logarithmus einfach weg und wählt die dann etwas schlampige Schreibweise "\(\log(.)\)", wobei je nach Notation auch damit der natürliche Logarithmus gemeint sein kann.