Source code online books for professionals by professionals

c) F(n) £ cf (n) and G(n) £ cg(n). (Do you see why it’s OK to use the same c for both?) That means that, for large 
enough n, we will have F(n) + G(n) £ c·( f (n) + g(n)), which simply means that F(n) + G(n) is O( f (n) + g(n)), which 
is what we wanted to prove. The f · g case is mostly equivalent (with a little wrinkle related to the c). Showing that 
max(Q( f ), Q(g)) = Q(max( f, g)) follows a similar logic. The most surprising fact may be that f + g is O(max( f, g)), or 
max( f, g) is W( f + g)—that is, that maximum grows at least as fast as a sum. This is easily explained by the fact that  
f + g £ 2 · max( f, g).
2-9. When showing equivalence of statements like this, it’s common to show implication from one to the next through 
the list and then from the last to the first. (You might want to try to show some of the other implications directly as 
well; there are 30 to choose from.) Here are a couple of hints to get you started. 1Þ2: Imagine that the tree is oriented. 
Then every edge represents a parent–child relationship, and each node except the root has a parent edge, giving n – 1 
edges. 2Þ3: Build T gradually by adding the n – 1 edges one by one. You aren’t allowed to connect nodes already in T 
(it’s acyclic), so each edge must be used to connect a new node to T, meaning that it will be connected.
2-10. This is sort of an appetizer for the counting in Chapter 3, and you can prove the result by induction (a technique 
discussed in depth in Chapter 4). There is an easy solution, though (which is quite similar to the presentation in 
Chapter 2). Give each parent (internal node) two imaginary ice cream cones. Now, every parent gives its children one 
ice cream cone each. The only one stuck without ice cream is the root. So, if we have n leaves and m internal nodes, 
we can now see that 2m (the number of ice cream cones, as specified initially) is equal to m + n – 1 (all nodes except 
the root, with one cone each), which means that m = n – 1. And this is the answer we’re looking for. Neat, huh? (This 
is an example of a nice counting technique, where we count the same thing in two different ways and use the fact that 
the two counts—in this case, the number of ice cream cones—must be equal.)
2-11. Number the nodes (arbitrarily). Orient all edges from lower to higher numbers.
2-12. The advantages and disadvantages depend on what you’re using it for. It works well for looking up edge weights 
efficiently but less well for iterating over the graph’s nodes or a node’s neighbors, for example. You could improve that 
part by using some extra structures (for example, a global list of nodes, if that’s what you need or a simple adjacency 
list structure, if that’s required).

---

Appendix d 
■
 Hints for exercises
275
Chapter 3
3-1. You could try doing this with induction or even recursion!
3-2. Start by rewriting to (n
2
–n)/2. Then first drop the constant factor, leaving n
2
–n. After that, you can drop the n, 
because it is dominated by n
2
.
3-3. Binary encoding shows us which powers of two are included in a sum, and each is included only once. Let’s say 
that the first k powers (or binary digits) let us represent any number up to 2
k
 – 1 (our inductive hypothesis; clearly true 
for k = 1). Now try to use the property mentioned in the exercise to show another digit (that is, being allowed to add in 
the next power of two) will let you represent any number up to 2
k+1
 – 1.
3-4. One of these is basically a for loop over the possible values. The other one is bisection, which is discussed in 
more detail in Chapter 6.
3-5. This is quite obvious from the symmetry in the numerator of the formula. Another way of seeing it is that there are 
as many ways of removing k elements as there are of leaving k elements.
3-6. The act of extracting sec[1:] requires copying n–1 elements, meaning that the running time of the algorithm 
turns into the handshake sum.
3-7. This quickly yields the handshake sum.
3-8. When unraveling the recursion, you get 2{2T(n–2) + 1} + 1 = 2
2