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