From 0064ce01edcdd2463864e7b3dfcb905962e41f0f Mon Sep 17 00:00:00 2001 From: Ramakrishnan Muthukrishnan Date: Fri, 17 Sep 2010 19:43:01 +0530 Subject: [PATCH] solution to 2.72 --- src/sicp/ex2_72.rkt | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) create mode 100644 src/sicp/ex2_72.rkt diff --git a/src/sicp/ex2_72.rkt b/src/sicp/ex2_72.rkt new file mode 100644 index 0000000..e9c06da --- /dev/null +++ b/src/sicp/ex2_72.rkt @@ -0,0 +1,22 @@ +#lang racket + +#| +Q: + +Consider the encoding procedure that you designed in exercise 2.68. What is the order of growth +in the number of steps needed to encode a symbol? Be sure to include the number of steps needed +to search the symbol list at each node encountered. To answer this question in general is difficult. + +Consider the special case where the relative frequencies of the n symbols are as described in +exercise 2.71, and give the order of growth (as a function of n) of the number of steps needed +to encode the most frequent and least frequent symbols in the alphabet. +|# + +#| +A. + +encode-symbol, has to go down to the last level, n is the depth of the tree, where n +is the number of symbols. On every node, it cons'es a number. Also there is the member? function +which spends max of n steps to find out if a given symbol is a member of the set. This is done for +every symbol in the message. So the worst case growth is of the order O(n * n). +|# -- 2.45.2