Master theorem

In the analysis of algorithms, the master theorem provides a cookbook solution in asymptotic terms (using Big O notation) for recurrence relations that occur in many divide and conquer algorithms. It was introduced and popularized by Introduction to Algorithms.

Examples with common algorithms

Algorithm Recurrence Big-Oh Solution
Binary Search T(n) = T(n/2) + O(1) O(log n)
tree traversal T(n) = 2 T(n/2) + O(1) O(n)
Mergesort T(n) = 2 T(n/2) + O(n) O(n log n)

source