Accumulation of Weight
Accumulation of Weight
- Solution of the problem requires all weight to be accumulated with one key
- All other keys must have weight zero
- Since weight accumulates to highest weight, weight can at most double with each comparison
- lg n comparisons are required to accumulate all weight