AdvancedMath for DSAUsed everywhere
Reading recurrences: T(n) = 2T(n/2) + n
Divide and conquer cost = (number of calls) × (work per call), level by level. Merge sort: log n levels × n work = O(n log n).
The idea
A recursive algorithm's cost is a recurrence: T(n) = a·T(n/b) + f(n) means a subcalls on inputs of size n/b plus f(n) work to split and combine.
Draw the call tree. Merge sort has log₂ n levels, and each level does n total work, so n log n. Binary search is T(n) = T(n/2) + 1: log n levels of O(1). Naive Fibonacci, T(n) = T(n−1) + T(n−2) + 1, doubles each level: about 2ⁿ.
Worked example
Three common recurrences
- T(n) = T(n/2) + O(1) → O(log n): binary search.
- T(n) = 2T(n/2) + O(n) → O(n log n): merge sort.
- T(n) = 2T(n/2) + O(1) → O(n): visiting every node of a tree.
In code (Python)
def merge_sort(nums): # T(n) = 2T(n/2) + n
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left, right = merge_sort(nums[:mid]), merge_sort(nums[mid:])
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
return merged + left[i:] + right[j:]Merge sort: O(n log n) time, O(n) space.
How to spot it
- Any recursion that splits the input: sorting, tree traversals, quickselect, “divide in half”.
Common mistakes
- Counting only one level's work.
- Assuming every split is even: quicksort's worst case is T(n) = T(n−1) + n = O(n²).
Where it comes up
Go further
Up next for you · Beginner
“Have I seen this?” is a set →