src/sicp/ex2_72.rkt

   1 #lang racket
   2
   3 #|
   4 Q:
   5
   6 Consider the encoding procedure that you designed in exercise 2.68. What is the order of growth
   7 in the number of steps needed to encode a symbol? Be sure to include the number of steps needed
   8 to search the symbol list at each node encountered. To answer this question in general is difficult.
   9
  10 Consider the special case where the relative frequencies of the n symbols are as described in
  11 exercise 2.71, and give the order of growth (as a function of n) of the number of steps needed
  12 to encode the most frequent and least frequent symbols in the alphabet.
  13 |#
  14
  15 #|
  16 A.
  17
  18 encode-symbol, has to go down to the last level, n is the depth of the tree, where n
  19 is the number of symbols. On every node, it cons'es a number. Also there is the member? function
  20 which spends max of n steps to find out if a given symbol is a member of the set. This is done for
  21 every symbol in the message. So the worst case growth is of the order O(n * n).
  22 |#