exercise-72.scm (533B)
1 ;; Exercise 2.72 2 3 ;; For n symbols, best case scenario would be 1 if we first look at the right 4 ;; branch n-1 if we first look at the left branch. O(1) or O(n) running time 5 ;; to encode the most frequent symbol. 6 ;; 7 ;; The worst case scenario would be: 8 ;; n-1 (or 1 plus n-1 (n) if we first look at the left branch?) for the first lookup 9 ;; n-2 (or 1 plus n-2 (n-1) if we first look at the left branch?) for the second. 10 ;; ... 11 ;; 1. (or 1 plus one (2) if we first look at the left branch?) 12 ;; Which is O(n^2) running time, right, no?