[prev] [prev-tail] [tail] [up]

3.7.4 Master Theorem

Knowledge Base > Algorithm > Recurrence

Master theorem method provides us a ’cookbook’ method for solving recurrences of the form

n T(n) = a⋅T(b-)+ f(n)
, where a ≥ 1 and b > 1 are constants and f(n) is an asymptotically positive function.[1]

Theorem 3.7.4.1. Master Theorem Let a ≥ 1 and b > 1 be constants, let f(n) be a function, and let T(n) be defined on the negative integers by the recurrence

T(n) = a⋅T(n-)+ f(n) b
Then T(n) can be bounded asymptotically as follows,
logb(a-ε) logba f(n) = O (n ),∃ε > 0 ⇒ T(n) = Θ (n ) f(n) = Θ (nlogba),∃ε > 0 ⇒ T(n) = Θ (nlogba ⋅lg n) f(n) = Ω (nlogb(a+ε)),∃ε > 0 AND n- a ⋅f(b) ≤ c ⋅f (n ),∃c < 1,n ⇒ ∞ ⇒ T (n) = Θ(f(n)) (3.7.4)
Proof>

[prev] [prev-tail] [front] [up]