o(g lg u)? Where could a bound of o(g lg u) arise? Binary search over Odg u) things T)=7(a)+O(1) T(lgu)=T(lg)/2)+O(1) O(g lg c 2001 by erik D. Demaine Introduction to Algorithms Day 23 L12.4© 2001 by Erik D. Demaine Introduction to Algorithms Day 23 L12.4 O(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) u