Source code online books for professionals by professionals

Figure 3-6.  A perfectly balanced, regular multiway (a-way) tree illustrating divide and conquer recurrences

---

ChapTer 3 
■
 CounTIng 101
62
Now the leaves dominate the picture. What total running time do you think that leads to? That’s right:
T n
n
b
a
( )
(
)
log
ÎQ
Take, for example, the following recurrence:
T n
T n
n
( )
( / ) lg
=
+
2
2
Here a = b, so we get a leaf count of n, which clearly grows asymptotically faster than f (n) = lg n. This means that 
the final running time is asymptotically equal to the leaf count, or Q(n).
Note
 
■
  To establish dominance for the root, we needed the extra requirement af (n/b) 
£ cf (n), for some c < 1.  
To establish leaf dominance, there is no similar requirement.
The last case is where the work in the root and the leaves has the same asymptotic growth:
f n
n
b
a
( )
(
)
log
ÎQ
This then becomes the sum of every level of the tree (it neither increases nor decreases from root to leaves), 
which means that we can multiply it by the logarithmic height to get the total sum:
T n
n
n
b
a
( )
(
lg )
log
ÎQ
Take, for example, the following recurrence:
T n
T n
n
( )
( / )
=
+
2
4
The square root may seem intimidating, but it’s just another power, namely, n
0.5
. We have a = 2 and b = 4, giving 
us logb a = log
4
 2 = 0.5. What do you know—the work is Q(n
0.5
) in both the root and the leaves, and therefore in every 
row of the tree, yielding the following total running time:
T n
n
n
n n
b
a
( )
(
lg )
(
lg ).
log
Î
=
Q
Q
Table 
3-2
 sums up the three cases of the master theorem, in the order they are customarily given: Case 1 is when 
the leaves dominate; case 2 is the “dead race,” where all rows have the same (asymptotic) sum; and in case 3, the root 
dominates.

---

ChapTer 3 
■
 CounTIng 101
63
So What Was All That About?
OK, there is a lot of math here but not a lot of coding so far. What’s the point of all these formulas? Consider, for a 
moment, the Python programs in Listings 3-1 and 3-2.
7
 (You can find a fully commented version of the mergesort 
function in Listing 6-6.) Let’s say these were new algorithms, so you couldn’t just search for their names on the Web, 
and your task was to determine which had the better asymptotic running time complexity.