walker...to the next step

((A 16) (B 8) (C 4) (D 2) (E 1))
(
 (
  (
   (
    (leaf E 1)
    (leaf D 2)
    (E D)
    3)
   (leaf C 4)
   (E D C)
   7)
  (leaf B 8)
  (E D C B)
  15)
 (leaf A 16)
 (E D C B A)
 31)
                                                                              
We'll demonstrate by the case when n=5 as showed above. The most frequent
symbol is A and the least frequent one is E.
                                                                              
Note that if we assume the built-in procedure "member" is theta(n), then
choose-bit-and-branch is theta(n). Let's assume so because "member" needs to
go through the whole list to check membership.
                                                                              
From exercise 2.71, we already know n equals the depth of the tree. It's also
obivious that the number of recursive calls of encode-symbol equals to the
level of the symbol in the tree minus one. For example, A is on the 2nd
level, so encode-symbol is called once. The idea is that each time
encode-symbol gets called, it goes down one level.
                                                                              
So, for the most frequent symbol, encode-symbol always gets called once, thus
choose-bit-and-branch is always called once. So it's theta(n).
                                                                              
Then for the least frequent symbol, encode-symbol always gets called n-1
times since the symbol is on the bottom. Each time it gets called,
choose-bit-and-branch gets called, too. Since choose-bit-and-branch is
theta(n), the whole effect is clearly theta(n^2).