Solutions to fixed -universe successor problem Goal: maintain a dynamic subset s of size n of the universe 0=10, 1,.,u-1 of size u subject to Insert DELeTE, SUCCESSoR PrEdeCessor Balanced search trees can implement operations in O(g n)time, without fixed-universe assumption In 1975. peter van Emde boas solved this problem in odg lg u time per operation If u is only polynomial in n, that is, u=o(n), then o(g lg n) time per operation exponential speedup c 2001 by erik D. Demaine Introduction to Agorithms Day 23 L12.3© 2001 by Erik D. Demaine Introduction to Algorithms Day 23 L12.3 Solutions to fixed-universe successor problem Goal: Maintain a dynamic subset S of size n of the universe U = {0, 1, …, u – 1} of size u subject to INSERT, DELETE, SUCCESSOR, PREDECESSOR. • Balanced search trees can implement operations in O(lg n) time, without fixed-universe assumption. • In 1975, Peter van Emde Boas solved this problem in O(lg lg u) time per operation. • If u is only polynomial in n, that is, u = O(nc), then O(lg lg n) time per operation-- exponential speedup!