SICP問題2.72

n記号のエンコードに関して、それぞれの記号をエンコードする際に木を探索するのに必用なステップ数はエンコード後のステップ数に比例するから増加の程度は
最大頻度の記号の場合は Θ(1)
最小頻度の記号の場合は Θ(n - 1)
となる。

と思ったんだけど、他の人のをカンニングしていると全然違うっぽい。

最大頻度の記号のエンコードに掛る手間は

encode-symbolの呼出しは、   2 回
symbol-exists?の呼出しは、n+1 回

最小頻度の記号のエンコードに掛る手間は

encode-symbolの呼出しは、   n 回
symbol-exits?の呼出しは、   n 回

ex-2.72|SICP|OSS-Web

ということで、最大頻度の場合の増加の程度はΘ(1)で良いけど、最大頻度の場合はencode-symbolの呼び出しの中でsymbol-exists?の呼び出しも同じ回数発生するのでΘ(n^2)ということっぽいです。