Rezidivbeziehungen nach Substitutionsverfahren?

Question

Ich habe: T (n) = T (n/2) + T (n/4) + T (n/8) + cn; c> 0

Dies ist mein Induktionsschritt: Want T (n) ist in O (n), dh einige d> 0 und n0, so dass jedes n> n0 und T (n) < dn beweisen

T (n) = T (n/2) + T (n/4) + T (n/8) + cn < = d (n/4) + d (n/4) + d (n/8) + cn = dn (7/8) + cn = dn (7/8) + cn < = dn ... = 8c < = d

ich stecken bleiben für den Basisfall, aber das ist wie mein Lehrer es mir erklärte: Base case: n0 muss klein genug sein, damit es tr ist y. Versuchen n0 = 8 T (8) = T (4) + T (2) + T (1) + c8 < = 8T (4) + 8T (2) + 8T (1) + C8 < d8

Kann mir jemand den Basisfall erklären? Vielen Dank!

Answer 1

Für Basisfall T(8) können wir annehmen, dass die Operationen endlich sind. so würde die Laufzeit O(1) (konstante Zeit) sein. weil Sie die Anzahl der Operationen zählen können.