Master theorem
Jump to navigation
Jump to search
MASTER THEOREM
Let a ≥ 1 and b > 1 be constants, let f(n) be a function, and let T(n) be defined on the nonnegative integers by the recurrence
T(n) = aT(n/b) + f(n),
where we interpret n/b to mean either ⌊n/b⌋ or ⌈n/b⌉. Then T(n) can be bounded asymptotically as follows.