Worst-case recursion tree 7(n)=7(0)+7(n-1)+cn cn ∑k|=(n2) 7(0)c(n-2
Worst-case recursion tree T( n) = T(0) + T( n − 1) + cn cn T(0) c ( n − 1) T(0) c ( n − 2) T(0) Θ(1) . . . 2 1 ( ) n k k n = ⎛ ⎞ Θ =Θ ⎜ ⎟ ⎝ ⎠ ∑
Worst-case recursion tree 7(n)=7(0)+7(n-1)+cn cn ∑k|=(n2) h=n⊙(1)c(n-2
Worst-case recursion tree T( n) = T(0) + T( n − 1) + cn cn Θ(1) c ( n − 1) Θ(1) c ( n − 2) Θ(1) Θ(1) . . . h = n 2 1 ( ) n k k n = ⎛ ⎞ Θ =Θ ⎜ ⎟ ⎝ ⎠ ∑
Nice-case analysis If were lucky, PaRTItiON Splits the array evenly 7(n)=27(n/2)+(n) o(nlg n)(same as merge sort) What if the split is al ways (n)=T(10n)+7(10n)+(m)
Nice-case analysis If we're lucky, PARTITION splits the array evenly: T( n) = 2 T( n/2) + Θ ( n ) = Θ ( nlg n ) (same as merge sort) What if the split is always : ? T( n) = T( n) + T( n) + Θ ( n ) 1 10 9 10 1 10 9 10
Analysis of nice case cn 81 n n cn 100 100 100 109 81 729 10001000 cn ≤cn 1---≤cn Total: O(nign)
Analysis of nice case n 1 . . . lg10 n cn cn cn ≤ cn Total: O (nlgn ) 1 10 n 9 10 n 1 100 n 9 100 n 9 100 n 81 100 n . . . . . . . . . . . . . . . 81 1000 n 729 1000 n . . . . . . . . . . . . cn cn 1 ≤ cn lg10/9 n
Randomized quicksort Partition around a random element around at where t chosen uniformly at random from ip...rI RANDOMIZED-PARTITION(A,P, r) 1.i← RAMDOM(p,r) 2. exchange Ar]←A[i 3. return PARTITION(A, p, r) We will show that the expected time is o(nign
Randomized quicksort RANDOMIZED-PARTITION (A, p, r ) 1. i ← RAMDOM (p, r ) 2. exchange A [ r] ↔ A [ i ] 3. return PARTITION (A, p, r ) We will show that the expected time is O (nlgn ) Partition around a random element around A [ t ], where t chosen uniformly at random from {p … r }