O(log n)

Wissenschaft Physik
1

Seien n0 element der Menge der Natürlichen Zahlen einschließlich Null und N0
= 2^n0. Zeigen Sie: Gilt für jedes N = 2^n (n element der Menge der
natürlichen Zahlen einschließlich Null, n >= n0) für die Zeit T(N), die ein
Algorithmus zur Bearbeitung einer N-elementigen Menge benötigt, T(N0) =
const (>0) und für N>N0

T(N) 0)

so ist T eine O(log N)-Funktion.

Wenn ich jetzt anfange zu rechnen:
T(N) = T(2^n)

2

Aber wie mache ich jetzt weiter?!? Hilfe!

Wieso? Du bist doch schon fertig. Die Zeit ist linear in n=lb(N)=log(N)/log(2). Die Konstante K=T(N0)-k*c kann durch |K|*log(N) abgeschaetzt werden (fuer grosse N>2, und nur um die geht es), alles weitere nach Definition.

Ein Induktionsbeweis kommt uebrigens immer gut an.

Ciao Lutz