Master Theorem (form)
Analyzes running time of divide-and-conquer algorithms.
Formula
Variables
Example
Merge sort solves T(n) = 2T(n/2) + n, which the Master Theorem gives as O(n log n).
How it works
This recurrence models an algorithm that splits one problem of size n into a equal subproblems, each of size n/b, then spends f(n) extra work combining the results. The reason the Master Theorem works is that it compares the total work done across the recursion tree: how much is spent across all subproblems at each level versus how quickly that work shrinks or grows from level to level. That comparison lets you determine whether the leaves, the internal levels, or the combine step dominate the asymptotic runtime.
When to use it
Use this when analyzing divide-and-conquer algorithms that recurse into a fixed number of equal-sized subproblems and have a separate nonrecursive combine cost. Common examples include recursive sorting, tree-based algorithms, FFT-style recurrences, and many geometric or dynamic-programming divide-and-conquer routines.
Worked example, step by step
Consider T(n) = 3T(n/2) + n^2. Step 1: Identify the parameters: a = 3, b = 2, and f(n) = n^2. Step 2: Compute n^(log_b a) = n^(log_2 3) ≈ n^1.585. Step 3: Compare f(n) with n^(log_b a): n^2 grows faster than n^1.585. Step 4: Check the regularity condition for Master Theorem case 3: a f(n/b) = 3(n/2)^2 = 3n^2/4, and 3n^2/4 <= c n^2 for some c < 1, so the condition holds. Step 5: Therefore T(n) = Θ(n^2). Final answer: the recurrence solves to Θ(n^2).
Common mistakes to avoid
- Comparing f(n) to a^n or b^n instead of comparing it to n^(log_b a)
- Forgetting that the subproblem size is n/b, not n-a or n-b
- Applying the theorem when subproblems are not equal-sized or when the recurrence does not match the required form
Did You Know?
The Master Theorem instantly gives the runtime of divide-and-conquer algorithms like merge sort.
Share this formula
More in Computer Science
View allShannon Entropy
AdvancedAverage information content of a random source (bits).
Hamming Distance
AdvancedNumber of positions at which two strings differ.
Bits to Represent n
BasicMinimum number of bits to represent n distinct values.
Binary to Decimal
BasicConverts a binary number to decimal.
Nodes in a Full Binary Tree
IntermediateTotal nodes in a perfect binary tree of height h.
Decimal to Binary
BasicConvert a decimal number to binary by dividing by 2 and reading remainders.