Master Method

DnC always involve a general pattern as it is defined in overview section. By defining such recurrence relations in a strong mathematical interpretation, as the Master Method, we can eliminate the duplication of solving new DnC instances.

Theorem

• Things to know:

  1. branching factor a: number of sub-problems branching from one.

  2. recursion tree depth k = logbn.

  3. size of a sub-problem: n/bk.

  define a typical DnC complexity by: Τ(n) = aΤ(n/b) + Ο(nd) for a > 0, b > 1, d ⩾ 0

  Figure 1. Problem of size n is divided into a sub-problems of size n/b

With that in mind, we formulate a theorem:

Figure 2. Master Method Theorem

Proof: Evaluate the complexity of DnC problem at level k would yield:

ak number of sub-problems, and each of size n/bk, therefore, the asymptotic complexity in the k th level would be:

ak ⋅ Ο(n/bk)d = Ο(nd) ⋅ (a/bd)k, k = 0, 1, ...logbn

Recall from the Geometric Series Sum:

1 + 𝔯 + 𝔯2 + ... + 𝔯n = (𝔯k+1 - 1) / 𝔯 - 1

Combining the k series:

Τ(n) = (logbn + 1) ⋅ Ο(nd) ⋅ (1 + (a/bd) + (a/bd)2 + ..+(a/bd)logbn),

Τ(n) = с ⋅ Ο(nd) ⋅ ((a/bd)logbn + 1 - 1) / ((a/bd) - 1)

• a/bd = 1, Τ(n) = Ο(nd ⋅ log(n))

• a < bd, Τ(n) ⩽ Ο(nd) ⋅ (1 / 1- (a/bd)), Τ(n) = Ο(nd)

• a > bd, Τ(n) ≈ Ο(nd ⋅ (a/bd)logbn) = Ο(nd ⋅ b-d ⋅ logbn ⋅ alogbn) = Ο(alogbn) = Ο(nlogba)

The theorem holds, proof ends.