Intuition for analysis (All our analyses today assume that all elements are distinct Lucky 7(n)=7(97/10)+e(m)nog091=n0=1 (n) case 3 Unlucky: 7(n)=7(n-1)+(n arithmetic series ⊙(n2) Worse than sorting o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.5© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.5 Intuition for analysis Lucky: 1 log10/ 91 0 n = n = CASE 3 T(n) = T(9n/10) + Θ(n) = Θ(n) Unlucky: T(n) = T(n – 1) + Θ(n) = Θ(n2) arithmetic series Worse than sorting! (All our analyses today assume that all elements are distinct.)