3) Recursion Define high(x)≥0 and low(x)≥0 so that x=high(xww+ low(x) INSERT(, w if sub thigh(x)] is empty then INSerT(high(x), summary)) INSERT(LoW(), subWlhigh(xD Running time Tu)=2 Tu)+o(1 T(lg)=2T(lga)/2)+O(1) O(g u) c 2001 by erik D. Demaine Introduction to Algorithms Day23L12.13© 2001 by Erik D. Demaine Introduction to Algorithms Day 23 L12.13 (3) Recursion INSERT(x, W) if sub[W][high(x)] is empty then 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) . u Define high(x) ≥ 0 and low(x) ≥ 0 so that x = high(x) W + low(x)