, hvor - drivende funksjon - vannskillefunksjon

Bevis - Masterteoremet

Run time

if there exists an such that:

Case 1: → Aka

Case 2: = →

Case 3: → Aka (Case 3 also has to satisfy the regularity condition for some constant and all n

Regularity Condition

Link to original


Exception of case 2: if then


Examples

Vannskillefunksjonen blir: → og siden f(n) inneholder et logaritmisk ledd blir →

Siden er lik vannskillefunksjonen blir →

Given

→ Since Then