Smatchcube's website 🌍


Exercise 2.72

This kind of question is really difficult, my answer is a big approximation.
We will give the order of growth in the case the tree is shaped as in the previous exercise.
The answer is dependent of my encode-symbol procedure so here is mine:

For the most frequent element we only need to check in the element is in the tree and if the first left branch contain the most frequent element so the order of grow of the number of steps needed to encode the most frequent element is \((n)\) (for checking if the element is in the “alphabet”).
For the least frequent element the order of growth is also \((n)\) (but requiring two times more steps than for the most frequent element) because we need to check if the element is in the tree and then traverse the tree of depth \(n\) checking if the element is in the left branch containing each time only one element.
My encode-symbol procedure is really optimized for this kind of tree.