Work Note 17, DM206, fall 2008

Exercises December 12

1. For van Emde Boa Trees we needed that T(n)=T(√n)+1 had solution T(n)∈O(loglog n) and were motivated by the fact that T(n)=2T(√n)+1 had solution T(n)∈Ω(log n). Prove these two facts.
2. At the lecture, when discussing dynamization, we proposed deleting elements from a structure by justing marking them as being deleted. Assume that every time we have completely rebuild the structure with n elements, we wait n/2 operations and then rebuild again. Given that construction time is O(n log n), define a potential function to show that deletion is amortized O(log n), while insertion remains amortized O(log² n) and searching remains O(log² n).
3. Problem sheet 1 for work note 17.
4. Problem sheet 2 for work note 17.