Improvements Need to reduce insert and successor down to 1 recursive call each lcl:7(2)=17n)+1) -o(g Ig n 2cal:()=2)+O() -O(g n) 3cl:()=37(a)+O(1) =O(lg)23) Were closer to this goal than it may seem! c 2001 by erik D. Demaine Introduction to Agorithms Day23L12.15© 2001 by Erik D. Demaine Introduction to Algorithms Day 23 L12.15 Improvements • 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) u Need to reduce INSERT and SUCCESSOR down to 1 recursive call each. We’re closer to this goal than it may seem!