In der Ungleichung
logan≤n
hängt das N, ab dem die Ungleichung für alle n≥N erfüllt ist, von a ab. Hat man aber für jedes a so ein N gefunden, dann ist O(logan)≤O(n) bewiesen. Und zwar wohlgemerkt mit Wahl von c=1.
Es könnte sich als schwierig erweisen, für jedes a ein geeignetes N zu finden. Deshalb sucht man zunächst nur ein N für den Fall a=2. Hier ist N=0 eine geeignete Wahl. Man zeigt also zunächst nur die Ungleichung
log2n≤n
für alle n≥0. Und zwar auch hier wohlgemerkt mit Wahl von c=1. Das ist vermutlich der Teil wo ihr vollständige Induktion angewendet habt.
Mit Basiswechel (siehe Satz unten) kann man dann argumentieren: Für alle n≥0 gilt
⟹⟹log2nlog2alog2nlogan≤n≤log2a1⋅n≤log2a1⋅n∣ : log2aBasiswechsel
Damit ist O(logan)≤O(n) bewiesen mit Wahl von c=log2a1 und N=0.
Satz (Basiswechsel). Seien p,q>0 mit p=1 und q=1 und r>0. Dann ist
logpr=logqplogqr
Beweis. Sei x∈R mit px=r. Dann gilt einerseits
pxlogp(px)x=r=logpr=logpr∣logpDef. Logarithmus
und andererseits
pxlogq(px)xlogqpx=r=logqr=logqr=logqplogqr∣logq3. Logarithmusgesetz∣ : logqp.
Also ist auch
logpr=logqplogqr□
Dieser Satz besagt, dass sich die Funktionen
x↦logpx
und
x↦logqx
nur um den konstanten Faktor logqp1 unterscheiden.
logxb = logax/logab
Das stimmt so nicht. Schau noch mal in den Satz zum Basiswechsel rein.