Computer Algorithms II Lecture Notes

4 November 2008 • Greed in Practice

---

Somewhat less obscurely, consider the difference

optimal encoding size - optimal' encoding size

where optimal' is the same tree as optimal, except x and min₁ have been swapped. Because the only difference between optimal and optimal' is the positions of x and min₁, the difference reduces to

[ f(min₁)l_o(min₁) + f(x)l_o(x)) ] - [ f(min₁)l_o'(min₁) + f(x)l_o'(x) ]

Also because of the swapping, l_o'(x) = l_o(min₁) and l_o'(min₁) = l_o(x), clears l_o from the difference:

[ f(min₁)l_o'(x) + f(x)l_o'(min₁)) ] - [ f(min₁)l_o'(min₁) + f(x)l_o'(x) ]

which can be re-arranged to

[ f(min₁)l_o'(x) - f(min₁)l_o'(min₁)] + [ f(x)l_o'(min₁) - f(x)l_o'(x)) ]

One more re-arrangement gives

(f(min₁) - f(x)(l_o'(min₁) - l_o'(x))

Because f(min₁) ≤ f(x) and l_o'(x) ≤ l_o'(min₁), the product must be nonnegative, which means the greedy encoding size must be at most the optimal encoding size.

---

This page last modified on 24 January 2006.