(2)Split universe into widgets SUCCESSOR(x) look for successor of x within widget w wigh()( Ovu) starting after position low(x) if d successor found then return it else find smallest i> high(x) O(√l) for which W, is nonempty return smallest element in w }O(a) Running time T(u)=o(vu) c 2001 by erik D. Demaine Introduction to Algorithms Day23L12.10© 2001 by Erik D. Demaine Introduction to Algorithms Day 23 L12.10 (2) Split universe into widgets SUCCESSOR(x) look for successor of x within widget Whigh(x) starting after position low(x). if successor found then return it else find smallest i > high(x) for which Wi is nonempty. return smallest element in Wi O( ) u O( ) u O( ) u Running time T(u) = O( ) u