Introduction to Algorithms6.046J/18.401J/SMA5503Fixed-universesuccessor problemSolutions to fixed-universe successor problemO(lg lg u)?!(1) Starting point: Bit vector(2) Split universe into widgets(2) Split universe into widgets(2) Split universe into widgets(2) Split universe into widgets(2) Split universe into widgetsRevelation(3) Recursion(3) Recursion(3) RecursionImprovementsRecursive calls in successorReducing recursive callsin successor(4) Improved successor(4) Improved successorRecursive calls in insert(5) Improved insert(5) Improved insertDeletionIntroduction to Algorithms6.046J/18.401J/SMA5503Lecture 14Prof. Erik DemaineIntroduction to Algorithms October 30, 2002 L12.2© 2002 by Erik D. DemaineFixed-universesuccessor problemGoal: Maintain a dynamic subset S of size nof the universe U = {0, 1, …, u –1}of size usubject to these operations:• INSERT(x ∈ U \ S): Add x to S.• DELETE(x ∈ S): Remove x from S.• SUCCESSOR(x ∈ U): Find the next element in Slarger than any element x of the universe U.• PREDECESSOR(x ∈ U): Find the previouselement in S smaller than x.Introduction to Algorithms October 30, 2002 L12.3© 2002 by Erik D. DemaineSolutions to fixed-universe successor problemGoal: Maintain a dynamic subset S of size nof the universe U = {0, 1, …, u –1}of size usubject to INSERT, DELETE, SUCCESSOR, PREDECESSOR.• Balanced search trees can implement operations inO(lg n) time, without fixed-universe assumption.• In 1975, Peter van Emde Boas solved this problemin 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!Introduction to Algorithms October 30, 2002 L12.4© 2002 by Erik D. DemaineO(lg lg u)?!Where could a bound of O(lg lg u) arise?• Binary search over O(lg u) things• T(u) = T( ) + O(1)T’(lg u) = T’((lg u)/2) + O(1)= O(lg lg u)uIntroduction to Algorithms October 30, 2002 L12.5© 2002 by Erik D. Demaine(1) Starting point: Bit vectorBit vector v stores, for each x ∈ U,1 if x ∈ S0 if x ∉ Svx=Example: u = 16; n = 4; S = {1, 9, 10, 15}.0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15Insert/Delete run in O(1) time.Successor/Predecessor run in O(u) worst-case time.Introduction to Algorithms October 30, 2002 L12.6© 2002 by Erik D. Demaine(2) Split universe into widgetsCarve universe of size u into widgetsuW0, W1, …, W1−ueach of sizeu.Example: u = 16, 4=u.0 1 0 001230 0 0 0456710 1 08 9 10 110 0 0 112 13 14 15W0W1W2W3Introduction to Algorithms October 30, 2002 L12.7© 2002 by Erik D. Demaine(2) Split universe into widgetsCarve universe of size u into widgetsuW0, W1, …, W1−ueach of sizeu.W0represents 0, 1, …,1−u∈ U;W1represents12 −u∈ U;u,1+u, …,Wirepresents1)1( −+ ui∈ U;ui,1+ui, …,::W representsu – 1 ∈ U.uu −,1+− uu, …,1−uIntroduction to Algorithms October 30, 2002 L12.8© 2002 by Erik D. Demaine(2) Split universe into widgetsDefine high(x) ≥ 0 and low(x) ≥ 0so that x = high(x)That is, if we write x ∈ U in binary,high(x) is the high-order half of the bits,and low(x) is the low-order half of the bits.For x ∈ U, high(x) is index of widget containing xand low(x) is the index of x within that widget.u+ low(x).x = 9high(x)= 2low(x)= 11 0 0 10 1 0 001230 0 0 045670 1 1 08 9 10 110 0 0 112 13 14 15W0W1W2W3Introduction to Algorithms October 30, 2002 L12.9© 2002 by Erik D. Demaine(2) Split universe into widgetsINSERT(x)insert x into widget Whigh(x)at position low(x).mark Whigh(x)as nonempty.Running time T(n) = O(1).Introduction to Algorithms October 30, 2002 L12.10© 2002 by Erik D. Demaine(2) Split universe into widgetsSUCCESSOR(x)look for successor of x within widget Whigh(x)starting after position low(x).if successor foundthen return itelse find smallest i > high(x)for which Wiis nonempty.return smallest element in WiO( )uO( )uO( )uRunning time T(u) = O( ).uIntroduction to Algorithms October 30, 2002 L12.11© 2002 by Erik D. DemaineRevelationSUCCESSOR(x)look for successor of x within widget Whigh(x)starting after position low(x).if successor foundthen return itelse find smallest i > high(x)for which Wiis nonempty.return smallest element in WirecursivesuccessorrecursivesuccessorrecursivesuccessorIntroduction to Algorithms October 30, 2002 L12.12© 2002 by Erik D. Demaine(3) RecursionRepresent universe by widget of size u.Recursively split each widget W of size |W|into sub[W][Wsubwidgets sub[W][0], sub[W][1], …,Store a summary widget summary[W] of size representing which subwidgets are nonempty.W1−W.] each of sizeWWsummary[W]Wsub[W][0]Wsub[W][1]Wsub[W][ ]W…1−WIntroduction to Algorithms October 30, 2002 L12.13© 2002 by Erik D. Demaine(3) RecursionDefine high(x) ≥ 0 and low(x) ≥ 0so that x = high(x)W+ low(x).INSERT(x, W)if sub[W][high(x)] is emptythen INSERT(high(x), summary[W])INSERT(low(x), sub[W][high(x)])Running time T(u) = 2 T( ) + O(1)T’(lg u)= 2 T’((lg u) / 2) + O(1)= O(lg u) .uIntroduction to Algorithms October 30, 2002 L12.14© 2002 by Erik D. Demaine(3) RecursionSUCCESSOR(x, W)j ← SUCCESSOR(low(x), sub[W][high(x)])if j < ∞then return high(x)else i ← SUCCESSOR(high(x), summary[W])j ← SUCCESSOR(– ∞, sub[W][i])return iRunning time T(u) = 3 T( ) + O(1)T’(lg u)= 3 T’((lg u) / 2) + O(1)= O((lg u)lg 3) .uW+ jW+ jT( )uT( )uT( )uIntroduction to Algorithms October 30, 2002 L12.15© 2002 by Erik D. DemaineImprovementsNeed to reduce INSERT and SUCCESSORdown to 1 recursive call each.• 2 calls: T(u) = 2 T( ) + O(1)= O(lg n)u• 3 calls: T(u) = 3 T( ) + O(1)= O((lg u)lg 3)u• 1 call: T(u) = 1 T( ) + O(1)= O(lg lg n)uWe’re closer to this goal than it may seem!Introduction to Algorithms October 30, 2002 L12.16© 2002 by Erik D. DemaineRecursive calls in successorIf x has a successor within sub[W][high(x)],then there is only 1 recursive call to SUCCESSOR.Otherwise, there are 3 recursive calls:• SUCCESSOR(low(x), sub[W][high(x)])discovers that sub[W][high(x)] hasn’t successor.• SUCCESSOR(high(x), summary[W])finds next nonempty subwidget sub[W][i].• SUCCESSOR(– ∞, sub[W][i])finds smallest element in subwidget sub[W][i].Introduction to Algorithms October 30, 2002 L12.17© 2002 by Erik D. DemaineReducing recursive callsin successorIf x has no successor within sub[W][high(x)],there are 3 recursive calls:• SUCCESSOR(low(x), sub[W][high(x)])discovers that sub[W][high(x)] hasn’t