Maths/Big O notation

Recurrence relations

After thiswhat you will be able to doTurn T(n) = 2T(n/2) + n into a recursion tree and derive its n log n cost from n work on each of log n levels.

Questionwhat this lesson answersA recursive algorithm's cost is written in terms of its own cost on smaller inputs, so the cost equation refers to itself. How do you turn that self-reference into one plain cost, and why does splitting the work in half and combining the halves give n times log n?

Not coveredwhat this lesson leaves outWe solve one recurrence, the split-in-half-then-combine one, by drawing its tree and adding the levels. We do not give the general rule that reads the answer off any such recurrence.

Put the values in a list from smallest to largest. That job is called sorting. One useful way to do it begins by splitting the list into two equal groups. Put each group in order with the very same method. When both groups are ordered, look at their first remaining values, take the smaller one, and repeat until a new ordered list is full. That act of joining two ordered halves is called a merge.

The method has a strange feature. To sort a list of ${n}$ items, it first asks itself to sort two lists of ${\dfrac{n}{2}}$ items. An algorithm that starts itself again on smaller inputs is doing recursion. Each start of the method, whether it is the original start or one made by an earlier start, is a call. A list of one item needs no split because it is already ordered. The smallest input at which this self-starting process stops is called a base case. Breaking a job into pieces, solving the pieces in the same manner, and joining their answers is also called divide and conquer.

Write down the self-reference

Let ${T(n)}$ mean the total amount of work needed to sort a list of ${n}$ items. The two smaller sorts cost ${T\left(\dfrac{n}{2}\right)}$ each. The final merge has to visit the items across both halves once. The work of joining the solved halves back together is the combine step. A trip that looks at every item once is a pass, so the combine step costs about ${n}$ units of work. The cost therefore obeys

The first piece says there are two smaller sorts. The second says that, after they return, one pass joins their results. An equation that defines a cost using that same cost on smaller inputs is called a recurrence relation. The word relation matters here: this line does not yet hand us a plain number. It passes the question down to smaller versions of itself. The base case is where that passing finally ends, because its cost is taken as given rather than split again.

There are many ways to push symbols through a recurrence. For this one, drawing says more. Put the original call at the top. Beneath it put the two calls it starts on half-sized lists. The calls directly started by one call are its children. Beneath those sit four calls on quarter-sized lists, then eight calls on eighth-sized lists, until the one-item base cases appear. A picture of the calls made by a recursion is called a recursion tree. One horizontal row of that picture is a level.

Now read the work row by row. The top level has one merge of size ${n}$, so it has about ${n}$ units of combine work. The next level has two merges of size ${\dfrac{n}{2}}$. The level after that has four merges of size ${\dfrac{n}{4}}$. In each case, the number of calls and the size of each call trade against one another:

Every combine level does about ${n}$ work. That is the whole useful balance in this tree. More calls do not automatically mean more work, because each call has less input to combine. The bottom row has many one-item lists, but it is the stopping row, not another row of merges. If a one-item base case costs a fixed amount, all of them together add an amount that grows in step with n, which the earlier lessons called a linear term. The combine work is the part that explains the larger shape.

Count the equal rows

The only remaining question is how many combine levels there are. The input size goes from ${n}$ to ${\dfrac{n}{2}}$, then to ${\dfrac{n}{4}}$, and continues to halve until it reaches one. The logarithms lesson already counted that process: the number of halvings is ${\log_2 n}$. This lesson uses that count rather than deriving it again.

Use ${j}$ only as a label for the combine rows, starting at one. Adding the same ${n}$ work over all of those rows gives

So the total sorting cost is described, up to the base cases’ linear total, by

This is where the shape comes from. Splitting in half gives the ${\log_2 n}$ levels. Combining everything on each level gives the ${n}$. Neither factor was guessed from the code’s appearance: the tree separates them so they can be counted.

The written answer still says base two. That base is a real record of how the list was split. To write ${n \log n}$ instead, the base is deliberately dropped. The logarithms lesson showed that changing bases only multiplies a logarithm by a fixed constant. The earlier lesson on throwing away fixed multipliers is what permits that shorter form. It is a decision about what the growth comparison will stop distinguishing, not a claim that base two and every other base produce the same number of operations.

This tree solved one particular self-referential cost: two equal pieces and one full pass to join them. Change the number of pieces, or change the cost of joining them, and the balance between the work per row and the number of rows changes. In some shapes, one row contributes most of the total. The Master theorem door is the general rule for reading that answer from a recurrence’s shape without drawing every tree.