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