Question

Understand the Master’s Theorem, be able to use it in algorithm analysis. For instance,if the sorting algorithm split the array into 5 parts instead of two parts, how do you use the Master’s Theorem for the complexity analysis?

(extra info by professor: In what cases you need to have b with different a? You usually can choose a=b. However, for f(n), it could be different. )

I think the question wants calculating/proving the time complexity mathematically if the problem is divided into 5 sub problems)

Answer 1

Master Theorem is used to determine running time of algorithms (divide and conquer algorithms) in terms of asymptotic notations.
Consider a problem that be solved using recursion

function f(input x size n)
if(n > k)
solve x directly and return 
else
divide x into a sub-problems of size n/b
call f recursively to solve each sub-problem
Combine the results of all sub-problems

The above algorithm divides the problem into a subproblems, each of size n/b and solve them recursively to compute the problem and the extra work done for problem is given by f(n), i.e., the time to create the subproblems and combine their results in the above procedure.

So, according to master theorem the runtime of the above algorithm can be expressed as:

where n = size of the problem
a = number of subproblems in the recursion and a >= 1
n/b = size of each subproblem
f(n) = cost of work done outside the recursive calls like dividing into subproblems and cost of combining them to get the solution.

Not all recurrence relations can be solved with the use of the master theorem i.e. if

• T(n) is not monotone, ex: T(n) = sin n
• f(n) is not a polynomial, ex: T(n) = 2T(n/2) + 2ⁿ

This theorem is an advance version of master theorem that can be used to determine running time of divide and conquer algorithms if the recurrence is of the following form :-

T(n) aT (n/b)+ e(n logPn)

where n = size of the problem
a = number of subproblems in the recursion and a >= 1
n/b = size of each subproblem
b > 1, k >= 0 and p is a real number.

Then,

1. if a > b^k, then T(n) = θ(n^log_ba)
2. if a = b^k, then
   (a) if p > -1, then T(n) = θ(n^log_ba log^p+1n)
   (b) if p = -1, then T(n) = θ(n^log_ba loglogn)
   (c) if p < -1, then T(n) = θ(n^log_ba)
3. if a < b^k, then
   (a) if p >= 0, then T(n) = θ(n^k log^pn)
   (b) if p < 0, then T(n) = θ(n^k)

Time Complexity Analysis –

• Example-1: Binary Search – T(n) = T(n/2) + O(1)
  a = 1, b = 2, k = 0 and p = 0
  b^k = 1. So, a = b^k and p > -1 [Case 2.(a)]
  T(n) = θ(n^log_ba log^p+1n)
  T(n) = θ(logn)
• Example-2: Merge Sort – T(n) = 2T(n/2) + O(n)
  a = 2, b = 2, k = 1, p = 0
  b^k = 1. So, a = b^k and p > -1 [Case 2.(a)]
  T(n) = θ(n^log_ba log^p+1n)
  T(n) = θ(nlogn)
• Example-3: T(n) = 3T(n/2) + n²
  a = 3, b = 2, k = 2, p = 0
  b^k = 4. So, a < b^k and p = 0 [Case 3.(a)]
  T(n) = θ(n^k log^pn)
  T(n) = θ(n²)
• Example-4: T(n) = 3T(n/2) + log²n
  a = 3, b = 2, k = 0, p = 2
  b^k = 1. So, a > b^k [Case 1]
  T(n) = θ(n^log_ba )
  T(n) = θ(n^log₂3)
• Example-5: T(n) = 2T(n/2) + nlog²n
  a = 2, b = 2, k = 1, p = 2
  b^k = 1. So, a = b^k [Case 2.(a)]
  T(n) = θ(n^log_balog^p+1n )
  T(n) = θ(n^log₂2log³n)
  T(n) = θ(nlog³n)