Recurrence relations
Divide-and-conquer recurrences
Mergesort
T(n) = 2T(n/2) + O(n):=O(nlogn)
Binary search
T(n) = T(n/2) + O(1):=O(logn)
Fast heap construction
T(n) = 2T(n/2) + O(logn):=O(n)
T(n) = 2T(n/2) + O(n) := O(nlogn)T(n) = T(n/2) + O(1) := O(logn)T(n) = 2T(n/2) + O(logn) := O(n)