Source code online books for professionals by professionals

Figure 3-3.  The height and width (number of leaves) of a perfectly balanced binary tree
Exactly how enormous the difference between these two is can be hard to fathom. One strategy would be to 
simply accept that they’re extremely different—meaning that logarithmic-time algorithms are super-sweet, while 
exponential-time algorithms are totally bogus—and then try to pick up examples of these differences wherever you 
can. Let me give you a couple of examples to get started. First let’s do a game I like to call “think of a particle.” I think of 
one of the particles in the visible universe, and you try to guess which one, using only yes/no questions. OK? Shoot!
This game might seem like sheer insanity, but I assure you, that has more to do with the practicalities (such 
that keeping track of which particles have been ruled out) than with the number of alternatives. To simplify these 
practicalities a bit, let’s do “think of a number” instead. There are many estimates for the number of particles we’re 
talking about, but 10
90
 (that is, a one followed by 90 zeros) would probably be quite generous. You can even play this 
game yourself, with Python:
 
>>> from random import randrange
>>> n = 10**90
>>> p = randrange(10**90)
 

---

ChapTer 3 
■
 CounTIng 101
49
You now have an unknown particle (particle number p) that you can investigate with yes/no questions  
(no peeking!). For example, a rather unproductive question might be as follows:
 
>>> p == 52561927548332435090282755894003484804019842420331
False
 
If you’ve ever played “twenty questions,” you’ve probably spotted the flaw here: I’m not getting enough “bang for 
the buck.” The best I can do with a yes/no question is halving the number of remaining options. So, for example:
 
>>> p < n/2
True
 
Now we’re getting somewhere! In fact, if you play your cards right (sorry for mixing metaphors—or, rather, games) 
and keep halving the remaining interval of candidates, you can actually find the answer in just under 300 questions. 
You can calculate this for yourself:
 
>>> from math import log
>>> log(n, 2) # base-two logarithm
298.97352853986263
 
If that seems mundane, let it sink in for a minute. By asking only yes/no questions, you can pinpoint any particle 
in the observable universe in about five minutes! This is a classic example of why logarithmic algorithms are so  
super-sweet. (Now try saying “logarithmic algorithm” ten times, fast.)
Note
 
■
  This is an example of bisection, or binary search, one of the most important and well-known logarithmic  
algorithms. It is discussed further in the “Black Box” sidebar on the 
bisect
 module in Chapter 6.
Let’s now turn to the bogus flip side of logarithms and ponder the equally weird exponentials. Any example 
for one is automatically an example for the other—if I asked you to start with a single particle and then double it 
repeatedly, you’d quickly fill up the observable universe. (It would take about 299 doublings, as we’ve seen.) This 
is just a slightly more extreme version of the old wheat and chessboard problem. If you place one grain of wheat on 
the first square of a chessboard, two on the second, four on the third, and so forth, how much wheat would you get?
4
 
The number of grains in the last square would be 2
63
 (we started at 2
0
 = 1) and according to the sum illustrated in 
Figure 
3-2
, this means the total would be 2
64
–1 = 18,446,744,073,709,551,615, or, for wheat, about 5 · 10
14
kg. That’s a lot 
of grain—hundreds of times the world’s total yearly production! Now imagine that instead of grain, we’re dealing with 
time. For a problem size n, your program uses 2n milliseconds. For n = 64, the program would then run for 584,542,046 
years! To finish today, that program would have had to run since long before there were any vertebrates around to 
write the code. Exponential growth can be scary.
By now, I hope you’re starting to see how exponentials and logarithms are the inverses of one another. Before 
leaving this section, however, I’d like to touch upon another duality that arises when we’re dealing with our hare and 
tortoise: The number of doublings from 1 to n is, of course, the same as the number of halvings from n to 1. This is 
painfully obvious, but I’ll get back to it when we start working with recurrences in a bit, where this idea will be quite 
helpful. Take a look at Figure 
3-4
. The tree represents the doubling from 1 (the root node) to n (the n leaves), but I 
have also added some labels below the nodes, representing the halvings from n to 1. When working with recurrences, 
4
Reportedly, this is the reward that the creator of chess asked for and was granted ... although he was told to count each grain he 
received. I’m guessing he changed his mind.

---

ChapTer 3 
■
 CounTIng 101
50
these magnitudes will represent portions of the problem instance, and the related amount of work performed, for a 
set of recursive calls. When we try to figure out the total amount of work, we’ll be using both the height of the tree and 
the amount of work performed at each level. We can see these values as a fixed number of tokens being passed down 
the tree. As the number of nodes doubles, the number of tokens per node is halved; the number of tokens per level 
remains n. (This is similar to the ice cream cones in the hint for Exercise 2-10.)
= n
n
n
2
n
2
1
1
1