Splitting the Work in Half

Last timeWhat the Machine Is Holding While It Waits

Shrinking a problem by one gives a method as slow as the loop it replaced, and shrinking it by half gives something qualitatively different for the same three lines.

The same three lines, a different method

Everything so far has made the problem smaller by one. Take off the first

item, solve the rest, combine. The combining is cheap, the depth is the size

of the input, and the total work is roughly the same as a loop would have

done. The recursion was a way of writing the method, not a way of improving it.

Now change one thing. Instead of removing one item, cut the input in half,

solve both halves, and combine those. The code is barely different and the

method is not.

FIG 1Shaving one off against cutting in half

python

def biggest_one(xs):
    if len(xs) == 1:
        return xs[0]
    rest = biggest_one(xs[1:])  # depth equals the length
    return xs[0] if xs[0] > rest else rest
def biggest_half(xs):
    if len(xs) == 1:
        return xs[0]
    mid = len(xs) // 2
    left = biggest_half(xs[:mid])   # depth is the number of halvings
    right = biggest_half(xs[mid:])
    return left if left > right else right
nums = list(range(1, 100001))
print(biggest_half(nums))  # 100000, depth about 17
print(biggest_one(nums))  # RecursionError, long before it finishes

Both examine every item exactly once and both are correct. The first holds a hundred thousand calls and fails; the second holds about seventeen and finishes. For finding the largest value the halving buys only the depth, since the work is the same either way. For sorting it buys much more.

How many levels there are

The reason the depth collapses is worth seeing as a count rather than taking

on trust.

Start with a million items. One split gives pieces of half a million. The next

gives a quarter of a million. Each level halves the size, so after $k$ levels

the pieces have size $n / 2^k$ , and the splitting stops when that reaches one.

Setting $n / 2^k = 1$ gives $2^k = n$ , so $k$ is the number of times $n$ can be

halved, which is its logarithm in base two.

FIG 2The number of levels

: the number of items at the start
: the number of levels of splitting before the pieces are single items

For a million items that is about twenty levels, and for a thousand million it is about thirty. The number grows so slowly that the depth of a halving method is almost never worth thinking about, which is itself the thing to remember.

Where the work actually goes

The depth is the easy part. The cost of the method is in what happens at each

level, and it has a pleasant structure.

At the top level there is one piece of size $n$ , and merging its two halves

costs whatever the merging step costs on $n$ items. At the next level there

are two pieces of size $n/2$ , and merging each costs half as much, but there

are two of them, so the level costs the same in total. At the next there are

four pieces of a quarter the size. Every level costs the same, because the

pieces shrink exactly as fast as they multiply.

The lesson stops here

3 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents