Master Theorem

Q: How do I compare $f(n)$ with $n^{\log_b a}$?

First compute the exponent $\log_b a$. For $a = 7$ and $b = 2$ it is $\log_2 7 \approx 2.81$, so the bottom work is about $n^{2.81}$. Then compare growth rates. The extra work $f(n) = n^{2}$ grows more slowly than $n^{2.81}$, so the first case applies and $T(n) = \Theta(n^{2.81})$.

In one sentence: The master theorem tells you how long a program takes when it cuts a problem into smaller pieces, solves each piece and joins the answers.

$T(n) = a\, T(n/b) + f(n)$

Read it out loud: “T of n equals a times T of n divided by b, plus f of n. T of n is the running time for an input of size n. The letter a is the number of smaller pieces, b is how many times smaller each piece is, and f of n is the extra work of splitting the input and joining the answers.”

Before you start

The ideas and signs this page uses, explained from zero. For powers of ten, Greek letters and other notation in general, see Math basics.

Recursion and divide and conquer: A recursive method calls itself on a smaller input. Divide and conquer is the plan: cut a problem into smaller pieces, solve each piece with the same method, then combine the answers. For example, to sort 8 cards you can sort two piles of 4 cards each, then merge the two sorted piles into one.
The running time $T(n)$: $T(n)$ is the running time of the algorithm on an input of size $n$ , counted in basic steps rather than seconds. The letter $T$ stands for time. So $T(n/b)$ is the running time on a smaller input of size $n/b$ . Counting steps means the answer does not depend on one particular computer.
Fractions like $n/b$: A fraction bar means divide. An input of size $n$ cut into $b$ equal parts gives pieces of size $n/b$ . For $n = 1024$ and $b = 2$ , each half has size $1024 / 2 = 512$ . Dividing by $b$ again makes each piece smaller again, which is how a recursion moves toward the smallest pieces.
Logarithms, like $\log_b a$: A logarithm answers the question: what power must I raise the base to, to get this number? In $\log_b a$ the small number $b$ is the base, and the answer is the power of $b$ that gives $a$ . For example $\log_2 8 = 3$ , because $2^{3} = 8$ . The notation $\log_2 1024 = 10$ means that 1024 can be halved 10 times to reach 1.
Powers, like $n^{\log_b a}$: A power is repeated multiplication. $n^{2}$ means $n \times n$ . An exponent does not have to be a whole number: $n^{1}$ equals $n$ , and an exponent of 1.585 lies between 1 and 2, so $n^{1.585}$ grows faster than $n$ but more slowly than $n^{2}$ .
The symbol $\Theta$ (theta): The notation $\Theta(\cdot)$ , read ‘theta’, says that the running time grows at this rate, up to constant factors. For example, $\Theta(n \log n)$ means the time is at most, and at least, a constant times $n \log n$ for large inputs. It is a tight description, not only an upper limit.
Merge sort (background): Merge sort is a sorting method that splits a list in half, sorts each half the same way, and then merges the two sorted halves into one sorted list. Merging two sorted lists with a total of $n$ items takes about $n$ steps, because each item is looked at once.

What each symbol means

Symbol	Meaning
$T(n)$	The running time of the algorithm on an input of size $n$ , counted in basic steps such as comparisons and additions. It is a count, so it has no unit in this formula. For merge sort on 1024 items, the count is in the tens of thousands of steps.
$n$	The size of the input, a whole number that counts items, such as the number of numbers in a list. It has no unit. Typical textbook values are 8, 1024 or a million, because the size is what makes the running time grow.
$a$	The number of smaller subproblems made at each step, a whole number at least 1. A value of $a = 2$ means each problem splits into two smaller problems. It has no unit, and it counts pieces, not time.
$b$	The shrink factor: each subproblem has size $n/b$ , so $b$ tells you how many times smaller each piece is. It is a number greater than 1. For merge sort $b = 2$ , which means each half is half the size of the whole list.
$T(n/b)$	The running time of one subproblem, which has size $n/b$ . It is the same kind of count as $T(n)$ , applied to a smaller input. The formula uses it again and again, which is why the formula is called a recurrence.
$f(n)$	The extra work at one level, outside the recursive calls: splitting the input and combining the answers. It is measured in the same steps as $T(n)$ . For merge sort, merging two halves of a list of $n$ items costs $f(n) = n$ steps.

The formula piece by piece

$n/b$: The size of each smaller piece. If the input has $n$ items and it is cut into $b$ equal parts, each part has $n/b$ items. With $b = 2$ , a list of 1024 items splits into two lists of 512 items each.
$T(n/b)$: The running time to solve one smaller piece. It is the same kind of problem with a smaller input, so the same formula applies to it again. This is why the formula refers to itself, and why it is called a recurrence.
$a\, T(n/b)$: The total time for all $a$ smaller pieces together. If $a = 2$ , there are two pieces, so the total is two times the time for one piece. Each piece takes $T(n/b)$ , so $a$ pieces take $a$ times as long.
$f(n)$: The extra work done at this level, outside the smaller pieces: splitting the input and joining the answers. For merge sort, joining two sorted halves takes about $n$ steps, so $f(n) = n$ in this case.
$n^{\log_b a}$: The work at the very bottom of the recursion, measured against the input size. It comes from counting pieces: after $\log_b n$ levels there are $a^{\log_b n} = n^{\log_b a}$ pieces of size 1. The theorem compares this bottom work with $f(n)$ .
$T(n) = a\, T(n/b) + f(n)$: In one plain sentence: the running time on an input of size $n$ equals $a$ times the running time on a piece of size $n/b$ , plus the extra work $f(n)$ at this level.

What the formula is doing, and why

What goes in and what comes out. The formula $T(n) = a\,T(n/b) + f(n)$ is a recurrence. It writes the time for size $n$ in terms of the time for smaller sizes. You give the master theorem three things: $a$ , $b$ and $f(n)$ . It gives back the running time $T(n)$ in a clear form, such as $n \log n$ . The point is to solve the equation without drawing the whole recursion.

Why picture a tree? Start with the first problem of size $n$ at the top. After one split there are $a$ problems of size $n/b$ . After $k$ splits there are $a^{k}$ problems of size $n/b^{k}$ . The splitting stops when the pieces reach size 1, after $\log_b n$ levels. Each level does some work, and the question is which part of the tree costs the most in total.

Why three cases? The theorem compares $f(n)$ with the bottom work $n^{\log_b a}$ . If $f(n)$ grows clearly more slowly, the bottom work dominates and $T(n) = \Theta(n^{\log_b a})$ . If they grow at the same rate, each of the $\log_b n$ levels costs about the same, so $T(n) = \Theta(n^{\log_b a} \log n)$ . If $f(n)$ grows clearly faster, the top level dominates and $T(n) = \Theta(f(n))$ . The last case also needs a mild condition on $f$ , which holds for usual functions such as $n^{2}$ .

Why does the middle case have a log factor? When every level has the same total work, the total is the work per level times the number of levels. The number of levels is $\log_b n$ , and that is where the $\log n$ comes from. In merge sort each level merges a total of $n$ items, and there are $\log_2 n$ levels, so the total is $n \log n$ .

When the theorem does not apply. It covers only this exact shape: every piece has the same size $n/b$ , the numbers $a$ and $b$ are fixed, and $f$ is a simple function of $n$ . A recurrence such as $T(n) = T(n-1) + n$ subtracts 1 each time instead of dividing the input, so it needs another method, such as drawing the tree and adding up its levels.

An everyday picture

Think of a boss who splits a project between 2 managers. Each manager splits their part between 2 teams, and the teams split their work down to single workers. To judge where the effort goes, ask whether most of it sits in the many small jobs at the bottom, in the middle levels, or in the planning and reporting at the top. The master theorem asks this same question about the recursion tree, and it answers without drawing the whole tree.

Worked example: Merge sort: T(n) = 2T(n/2) + n

Merge sort splits a list of $n$ numbers into 2 halves, sorts each half the same way, and then merges the two sorted halves in about $n$ steps. So $a = 2$ pieces, each of size $n/b$ with $b = 2$ , and the merging work is $f(n) = n$ . The recurrence is $T(n) = 2\,T(n/2) + n$ .

Find the bottom exponent. We need $\log_b a = \log_2 2$ , which asks: what power of 2 gives 2? The answer is 1, because $2^{1} = 2$ . So the bottom work is $n^{\log_b a} = n^{1} = n$ .
Compare the two growth rates. The extra work is $f(n) = n$ , and the bottom work is also $n$ . Both grow in a straight line, at exactly the same rate. This is the middle case, where every level of the tree costs about the same amount.
Apply the middle case. The middle case adds a log factor, so $T(n) = \Theta(n^{\log_b a} \log n) = \Theta(n \log n)$ . In this example $\log n$ means $\log_2 n$ , which counts how many times the list can be halved.
Count the levels for $n = 1024$ . Halving 1024 gives 512, 256, 128, 64, 32, 16, 8, 4, 2 and finally 1. That is 10 halvings. Since $2^{10} = 1024$ , we have $\log_2 1024 = 10$ levels.
Find the work per level. Every level merges all the pieces on that level, and together the pieces hold all 1024 items. Merging costs about one step per item, so each level costs about 1024 steps. Over 10 levels the total is $10 \cdot 1024 = 10240$ steps, which is 10,240 steps.
Compare with the squared count. If the work grew like $n^{2}$ , the count for 1024 items would be $1024^{2} = 1048576$ steps. That is a little over 100 times the 10,240 steps that merge sort needs, which is why the difference matters for long lists.

Answer: Merge sort takes $\Theta(n \log n)$ time. For 1024 items that is about 10,240 steps, not the 1,048,576 steps that an $n^{2}$ method would need.

The numbers in this example are recomputed by script every time the site is built.

Common mistakes

Mixing up $a$ and $b$ . The number $a$ counts the smaller subproblems, and $b$ says how many times smaller each one is. Merge sort has $a = 2$ and $b = 2$ , so the two numbers look the same, which makes this easy to do.
Treating $f(n)$ as the total running time. $f(n)$ is only the work done at one level, outside the recursive calls. The total also includes all the smaller pieces, which the $a\,T(n/b)$ part adds.
Stopping at the middle case too early. When $f(n)$ grows at the same rate as $n^{\log_b a}$ , multiply by $\log n$ as well. The answer is $\Theta(n^{\log_b a} \log n)$ , not $\Theta(n^{\log_b a})$ .
Using the theorem on a recurrence that does not fit, such as $T(n) = T(n-1) + n$ . That one subtracts 1 each time instead of dividing the input by $b$ .

Where you will meet it

Analyzing merge sort, which splits a list in half, sorts each half and merges the results.
Binary search, where $T(n) = T(n/2) + 1$ gives $\Theta(\log n)$ time, because each step throws away half of the remaining items.
Strassen’s matrix multiplication, where $T(n) = 7\,T(n/2) + \Theta(n^{2})$ gives about $n^{2.81}$ time. That is faster for large matrices than the usual method, which takes about $n^{3}$ steps.
Karatsuba multiplication of large numbers, where $T(n) = 3\,T(n/2) + O(n)$ gives about $n^{1.585}$ time.

Questions people ask

Does the master theorem work for every recurrence?

No. It applies only to recurrences of the form $T(n) = a\,T(n/b) + f(n)$ , with a whole number $a \ge 1$ , a number $b > 1$ and a simple $f(n)$ . Other recurrences need a recursion tree or the substitution method, which checks a guessed answer with a proof.

How do I compare $f(n)$ with $n^{\log_b a}$?

First compute the exponent $\log_b a$ . For $a = 7$ and $b = 2$ it is $\log_2 7 \approx 2.81$ , so the bottom work is about $n^{2.81}$ . Then compare growth rates. The extra work $f(n) = n^{2}$ grows more slowly than $n^{2.81}$ , so the first case applies and $T(n) = \Theta(n^{2.81})$ .

Why does the middle case have a log n factor?

The recursion has $\log_b n$ levels. When each level does about the same total work, the total is that work times the number of levels. Multiplying the work per level by the number of levels gives the extra $\log n$ factor.

Big O Notation: Big O notation is a way to say that one function never grows faster than another, once the input is big enough.
Sum of the First n Integers: This formula gives the total of the numbers 1, 2, 3 and so on up to $n$ in one quick calculation, with no adding one number at a time.
Geometric Series: A geometric series adds up a list where each term is the one before it times a fixed number, and this formula finds the whole sum in one step.
Binary Search Steps: Binary search finds an item in a sorted list by checking the middle and throwing away half, and this formula counts how many checks that takes at most.