Divide and conquer algorithms typically have a time complexity recurrence relation of the form:

  • T(1) = c
  • T(n) = aT(n/b) + cnk
Such that a problem of size n is split into a subproblems, each of size n/b. And cnk is the cost of combining the solutions.

The closed form solution for this recurrence depends on the relation between a, and bk.

  • if a > bk then T(n) = O(nlogba)
  • if a = bk then T(n) = O(nklog n)
  • if a < bk then T(n) = O(nk)

For example, merge sort is a typical divide and conquer alorithm, where the list to be sorted is split into 2 equal subproblems and it takes O(n) time to put the two sorted sublists back together.

Thus the recurrence relation will be:
T(n) = 2T(n/2) + n
Where a = 2, b = 2, k = 1
Applying the above theorem, merge sort has a time complexity of O(n log n).

Reference: Lecture notes from my Theory of Algorithms class

Log in or register to write something here or to contact authors.