Design and Analysis of Algorithms

Prev

Next

Master's method

Master's method is used to solve the recurrence equation of an algorithm that uses Divide-and-conquer. Instead of using elaborate methods like recursion tree, substitution, etc., one can easily determine the complexity using quick computation.

The generalized recurrence equation for an algorithm that uses divide-and-conquer technique takes the following form.

    T(1) = 1
    T(n) = aT(n/b) + n^k

To solve a problem of size n, the algorithm breaks it down to a sub-problems each of size n/b, solves them individually and combines the solution. Each sub-problem is solved recursively solved in the same fashion until the sub-problem's size is 1. The term n^k denotes the time taken to break and merge while T(n/b) denotes the time taken to solve a sub-problem.

Lets try to apply substitution to solve this.

    T(n) = aT(n/b) + n^k
      = a[aT(n/b²) + (n/b)^k] + n^k
      = a²T(n/b²) + a(n/b)^k + n^k
      = a³T(n/b³) + a²(n/b²)^k + a(n/b)^k + n^k
      =     :
      =     :
      = a^log_bnT(1) + ... + a³(n/b³)^k + a²(n/b²)^k + a(n/b)^k + n^k
      = n^log_ba + n^k [a^logn-1/b^(logn-1)k... + a³/b^3k + a²/b^2k + a/b^k + 1]
      (log rule)       (log_bn terms)
      = n^log_ba + n^k [(a/b^k)^logn-1... + (a/b^k)³ + (a/b^k)² + a/b^k + 1]

The final recurrence equation is

    T(n) = n^log_ba + n^k [(a/b^k)^logn-1... + (a/b^k)³ + (a/b^k)² + a/b^k + 1]

Looking at the above recurrence equation, we note that the rhs is the sum of two terms. There are 3 cases to consider here. Master's method states that:

Case 1: If n^log_ba > n^k, then T(n) ∈ Θ(n^log_ba) since n^log_ba will dominate. Stated otherwise, the cost of solving the subproblems dominates the cost of breaking the problem and combining the solutions of subproblems.

Case 2: If n^log_ba < n^k, then T(n) ∈ Θ(n^k) since n^k will dominate. i.e. the cost of breaking the breaking the problem and combining the solutions of the subproblems dominates the cost of solving the subproblems.

Case 3: If n^log_ba = n^k, then T(n) ∈ Θ(n^k.logn) since there are logn terms.

Why did we append logn to case 3?

n^log_ba = n^k implies log_ba = k
This implies b^log_ba = b^k
This implies a^log_bb = b^k (applying logrithmic rule)
This implies a = b^k

Now consider the second term in the rhs of the recurrence equation: [(a/b^k)^logn-1... + (a/b^k)³ + (a/b^k)² + a/b^k + 1]. Since a = b^k, this reduces to (1 + 1 + ... + 1) = logn (as this is the sum of logn 1s). Therefore, the complexity is given by Θ(n^k.logn)

Why didn't we append logn to case 2?

Working out in the same manner, we now have a < b^k.
This implies a/b^k < 1.
This further implies, the series a²/b^2k, a³/b^3k, ....., a^logn-1/b^(logn-1)k goes on reducing. So, even though there are logn terms, they don't sum up to logn. Instead, the quantity can be treated as a constant.

Let's work out some examples. We assume T(1) = 1 always.

1) T(n) = 9T(n/3) + n

a = 9, b = 3 and k = 1
log_ba = log₃9 = 2 (greater than k)
Hence,T(n) = Θ(n²)

2) T(n) = T(2n/3) + 1

a = 1, b = 3/2 and k = 0
log_ba = log_3/21 = 0 (equal to k)
Hence, T(n) = Θ(log n)

3) T(n) = 3T(n/4) + n√n

a = 3, b = 4 and k = 1.5
log_ba = log₄3 < 1 (less than k)
Hence, T(n) = Θ(n^1.5)

Applicability of Master's method

Master's method can be applied to determine the complexity only if the recurrence equation is of the form T(n) = aT(n/b) + n^k. For instance, it cannot be used if we have aT(n-b) in place of aT(n/b) and/or instead of n^k we have some function f(n) which is not a 'pure' polynomial.

Determining time complexity for problems solved using decrease-and-conquer

Master's method dealt before gave a quick way to determine the complexity of problems solved using divide-and-conquer approach. i.e. a problem is solved by breaking it to a subproblems each of size n/b. In this section, we try to obtain a similar formula for determining the complexity of problems solved using decrease-and-conquer approach. A generalized recurrence equation for such a problem is given as follows:

    T(0) = T(1) = ... = T(b) = 1
    T(n) = aT(n-b) + n^k

Again, lets solve this using the substitution method.

  T(n) = aT(n-b) + n^k
      = a[aT(n-2b) + (n-b)^k] + n^k
      = a²T(n-2b) + a(n-b)^k + n^k
      = a³T(n-3b) + a²(n-2b)^k + a(n-b)^k + n^k
          :
          : (takes n/b steps till it hits T(1)
          :
      = a^n/bT(1) + a^n/b-1(n-(n/b-1)b)^k + ... + a²(n-2b)^k + a(n-b)^k + n^k
      <= a^n/b + a^n/b-1n^k + ... + a²n^k + an^k + n^k
      = a^n/b + n^k[a^n/b-1 + .. + a² + a + 1]
                  (n/b terms)
      = a^n/b + n^k(cn) (c is the sum of the terms which is a constant)
      = a^n/b + c.n^k+1

We see that the recurrence equation contains 2 terms. The first one a^n/b is exponential while the second one is polynomial. The second one is polynomial because we initially started with the recurrence equation that way. If we were to consider a more generalized recurrence equation:

  T(n) = aT(n-b) + f(n)

where f(n) can be polynomial, logarithmic or exponential, the closed form equation can be determined as

  T(n) = a^n/b + n.f(n)

Here too, there are three cases to consider.

Case 1: If a^n/b > n.f(n), then T(n) = O(aⁿ).

Case 2: If a^n/b < n.f(n), then T(n) = O(n.f(n)).

Special Case: If a = 1, then a^n/b = 1. Hence, T(n) = O(n.f(n)).

Note: It is highly unlikely that f(n) is exponential. Usually it is a constant, logarithmic or at worst a polynomial. Case 2 is extremely rare.

Recall the recurrence equations that we had worked out earlier.

1. Computing factorial, max element and number of binary digits in an integer.

      T(n) = T(n-1) + c

Here a = 1 and f(n) is a constant (special case). Hence T(n) = O(n), same as the one we derived earlier.

2. Tower of Hanoi

      T(n) = 2T(n-1) + 1

Here a = 2 and f(n) is a constant(case 1). Hence T(n) = O(2ⁿ), same as we derived.

Note: Recursive algorithms fall into either divide-and-conquer or decrease-and-conquer category.