In many cases we only care about the total time required to process a set of data, rather than the cost of processing any one individual element. In those cases, we can design data structures that make some operations more expensive in order to lower the total cost of all aggregate operations. How do you analyze these structures?
Readings
- CLRS Chapter 17.
Links