Master theorem

From Algowiki
Revision as of 20:21, 25 September 2014 by Lkw (talk | contribs) (→‎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.

1. If f (n) = O(nlogb a - ε) for some constant ε > 0, then T(n) = Θ(nlogb a).
2. If f (n) = Θ(nlog b a), then T(n) = Θ(nlogb a lg n).
3. If f (n) = Ω(nlogb a + ε) for some constant ε > 0, and if af(n/b) ≤ cf(n) for some constant c < 1 and all sufficiently large n, then T(n) = Ω(f (n)).