Analysis of expected time The analysis follows that of randomized quicksort, but it's a little different Let T(n)=the random variable for the running time of RaNd-SELECT on an input of size n assuming random numbers are independent For k=01. n-1. define the indicator random variable ks 1 if PartItion generates a k: n-k-1 sp pl 0 otherwise o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.6
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.6 Analysis of expected time Let T(n) = the random variable for the running time of RAND-SELECT on an input of size n, assuming random numbers are independent. For k = 0, 1, …, n–1, define the indicator random variable Xk = 1 if PARTITION generates a k : n–k–1 split, 0 otherwise. The analysis follows that of randomized quicksort, but it’s a little different
Analysis(continued) To obtain an upper bound, assume that the ith element al ways falls in the larger side of the partition T(max(0, n-1)+o(n) if0: n-1 split T(max1, n-2))+o(n) if 1: n-2 split T(max(n-1,0)+o(n ifn-1: 0 split 2X(T(maxk, n-k-1)+0(n) k=0 o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.7
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.7 Analysis (continued) T(n) = T(max{0, n–1}) + Θ(n) if 0 : n–1 split, T(max{1, n–2}) + Θ(n) if 1 : n–2 split, M T(max{n–1, 0}) + Θ(n) if n–1 : 0 split, ∑ ( ) − = = − − + Θ 1 0 (max{ , 1}) ( ) n k Xk T k n k n . To obtain an upper bound, assume that the ith element always falls in the larger side of the partition:
Calculating expectation E[T(m)=E∑Xk(T(max体.n-k-1)+(n) Take expectations of both sides o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.8
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.8 Calculating expectation ( ) = ∑ − − + Θ −=10 [ ( )] (max{ , 1}) ( ) nk E T n E Xk T k n k n Take expectations of both sides
Calculating expectation E[T(n)=E 2Xk(T(max(k,n-k-1)+O(n) k=0 k=o k((max(k, n-k-1)+O(n)7 ∑E[X Linearity of expectation o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.9
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.9 Calculating expectation ( ) ∑ [ ] ( ) ∑ − = − = = − − + Θ = − − + Θ 1 0 1 0 (max{ , 1}) ( ) [ ( )] (max{ , 1}) ( ) n k k n k k E X T k n k n E T n E X T k n k n Linearity of expectation
Calculating expectation E[T(m)=E∑x(7(max伙k,n=k-1)+(m) k=0 XELXk(T(max(k, n-k-1))+O(n) k=0 ZELXK.E[T(max k, n-k-1))+O(n) Independence of X, from other random choices o 2001 by Charles E Leiserson Introduction to Algorithms Day 9 L6.10
© 2001 by Charles E. Leiserson Introduction to Algorithms Day 9 L6.10 Calculating expectation ( ) [ ] ( ) ∑ [ ][ ] ∑ ∑ − = − = − = = ⋅ − − + Θ = − − + Θ = − − + Θ 1 0 1 0 1 0 (max{ , 1}) ( ) (max{ , 1}) ( ) [ ( )] (max{ , 1}) ( ) n k k n k k n k k E X E T k n k n E X T k n k n E T n E X T k n k n Independence of Xk from other random choices