7 Deamortization of dynamic tables It is sometimes possible to deamortize data structures, i.e., getting the...

Transcribed Image Text:

7 Deamortization of dynamic tables It is sometimes possible to deamortize data structures, i.e., getting the same bounds worst case as amortized by doing the work in the "background". Show that you can get worst case constant insertion time in dynamic tables, while still having space usage O(n), where n is the number of elements currently in the table. Hint. Use the doubling technique, but spread out the work on all the insertions. 7 Deamortization of dynamic tables It is sometimes possible to deamortize data structures, i.e., getting the same bounds worst case as amortized by doing the work in the "background". Show that you can get worst case constant insertion time in dynamic tables, while still having space usage O(n), where n is the number of elements currently in the table. Hint. Use the doubling technique, but spread out the work on all the insertions.

Answer rating: 100% (QA)

Amortized Analysis is used for algorithms where an occasional operation is very slow but most of the ... View the full answer