Source code online books for professionals by professionals

DOWN the raBBIt hOLe (Or ChaNGING OUr VarIaBLe)
a word of warning: The material in this sidebar may be a bit challenging. If you already have your head full with 
recurrence concepts, it might be a good idea to revisit it at a later time.
In some (probably rare) cases, you may come across a recurrence that looks something like the following:
 
T(n) = aT(n
1/b
) + f(n)
 
In other words, the subproblem sizes are b-roots of the original. Now what do you do? actually, we can move into 
“another world” where the recurrence is easy! This other world must, of course, be some reflection of the real 
world, so we can get a solution to the original recurrence when we come back.
our “rabbit hole” takes the form of what is called a variable change. It’s actually a coordinated change, where we 
replace both T (to, say, S) and n (to m) so that our recurrence is really the same as before—we’ve just written it 
in a different way. What we want is to change T(n
1/b
) into S(m/b), which is easier to work with. Let’s try a specific 
example, using a square root:
 
T(n) = 2T(n
1/2
) + lg n
 
how can we get T(n
1/2
) = S(m/2)? a hunch might tell us that to get from powers to products, we need to involve 
logarithms. The trick here is to set m = lg n, which in turn lets us insert 2m instead of n in the recurrence:
 
T(2m) = 2T((2
m
)
1/2
) + m = 2T(2
m/2
) + m
 
By setting S(m) = T(2
m
), we can hide that power, and bingo! We’re in Wonderland:
 
S(m) = 2S(m/2) + m
 
This should be easy to solve by now: T(n) = S(m) is 
Q(m lg m) = Q(lg n · lg lg n).
In the first recurrence of this sidebar, the constants a and b may have other values, of course (and f may certainly 
be less cooperative), leaving us with S(m) = aS(m/b) + g(m) (where g(m) = f (2
m
)). You could hack away at this 
using repeated substitution, or you could use the cookie-cutter solutions given in the next section, because they 
are specifically suited to this sort of recurrence.
The Master Theorem: A Cookie-Cutter Solution
Recurrences corresponding to many of so-called divide and conquer algorithms (discussed in Chapter 6) have the 
following form (where a ³ 1 and b > 1):
T n
aT n b
f n
( )
(
)
( )
=
/ +
The idea is that you have a recursive calls, each on a given percentage (1/b) of the dataset. In addition to the 
recursive calls, the algorithm does f (n) units of work. Take a look at Figure 
3-6
, which illustrates such an algorithm. In 
our earlier trees, the number 2 was all-important, but now we have two important constants, a and b. The problem 
size allotted to each node is divided by b for each level we descend; this means that in order to reach a problem size of 
1 (in the leaves), we need a height of log
b
 n. Remember, this is the power to which b must be raised in order to get n.

---

ChapTer 3 
■
 CounTIng 101
61
However, each internal node has a children, so the increase in the node count from level to level doesn’t 
necessarily counteract the decrease in problem size. This means that the number of leaf nodes won’t necessarily be n. 
Rather, the number of nodes increases by a factor a for each level, and with a height of log
b
 n, we get a width of a
log
b
 
n
. 
However, because of a rather convenient calculation rule for logarithms, we’re allowed to switch a and n, yielding n
log
b
 
a
 
leaves. Exercise 3-10 asks you to show that this is correct.
The goal in this section is to build three cookie-cutter solutions, which together form the so-called master 
theorem. The solutions correspond to three possible scenarios: Either the majority of the work is performed (that is, 
most of the time is spent) in the root node, it is primarily performed in the leaves, or it is evenly distributed among the 
rows of the recursion tree. Let’s consider the three scenarios one by one.
In the first scenario, most of the work is performed in the root, and by “most” I mean that it dominates the 
running time asymptotically, giving us a total running time of Q(f (n)). But how do we know that the root dominates? 
This happens if the work shrinks by (at least) a constant factor from level to level and if the root does more work 
(asymptotically) than the leaves. More formally:
af n b
cf n
(
)
( ) ,
/ £
for some c < 1 and large n, and
f n
n
b
a
( )
(
) ,
log
Î
+
W
e
for some constant 
e>0. This just means that f (n) grows strictly faster than the number of leaves (which is why I’ve 
added the 
e in the exponent of the leaf count formula). Take, for example, the following:
T n
T n
n
( )
( / )
.
=
+
2
3
Here, a = 2, b = 3 and f (n) = n. To find the leaf count, we need to calculate log
3
 2. We could do this by using the 
expression log 2/log 3 on a standard calculator, but in Python we can use the log function from the math module, and 
we find that log(2,3) is a bit less than 0.631. In other words, we want to know whether f (n) = n is W(n
0.631
), which it 
clearly is, and this tells us that T(n) is Q(f (n)) = Q(n). A shortcut here would be to see that b was greater than a, which 
could have told us immediately that n was the dominating part of the expression. Do you see why?
We can turn the root-leaf relationship on its head as well:
f n
O n
b
a
( )
(
)
log
Î
-
e
f(n)
f(n/b)
f(n/b)
1
1
1
···
log
b 
n
  
log
b
n
...
1
a
···
a
n
log
b 
a
=