3) Recursion SUCCESSOR(X, j< SUCCESSOR(Low(x), sub[ high(x) ifj<∞ then return high(x ese/← SUCCESSOR(high(x), summary)7√) j< SUCCESSOR(00, subw[i return i、W+ Running time Tu)=3 Tu)+O(1) (lg)=3T"(lg)/2)+o(1) O(g)23) c 2001 by erik D. Demaine Introduction to Algorithms Day23L12.14© 2001 by Erik D. Demaine Introduction to Algorithms Day 23 L12.14 (3) Recursion SUCCESSOR(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 i Running time T(u) = 3 T( ) + O(1) T’(lg u) = 3 T’((lg u) / 2) + O(1) = O((lg u)lg 3) . u W + j W + j T( ) u T( ) u T( ) u