2

I'm reading Introduction to Algorithms-Cormen, Leiserson, Rivest, Stein, Section 9.2 Selection in Expected linear time. Page-217

They have defined Indicator Random Variable $X_k$ as

$X_k$ = I {the subarray A[p..q] has exactly k elements}

and Random variable T(n) as

T(n) = the running time on an input array A[p..r] of n elements

then there is a para saying

For a given call of RANDOMIZED-SELECT, the indicator random variable $X_k$ has the value 1 for exactly one value of k, and it is 0 for all other k. When $X_k$ = 1, the two subarrays on which we might recurse have sizes k - 1 and n - k. Hence, we have the recurrence.

$T(n) \leq \sum_{k=1}^{n} X_k . (T(max(k-1, n-k))+O(n))$

$= \sum_{k=1}^{n} X_k . T(max(k-1, n-k))+O(n)$

I'm not getting how they have defined the above recurrence can anybody explain it to me.

Atinesh
  • 1,239

1 Answers1

0

Randomized-select is a recursive algorithm that partitions its input array using a random pivot, and proceeds to work on the partition containing the $i$-th smallest element of the original array. When the array has $n$ elements, the random pivot partitions the array into smaller arrays of size $k-1$ and $n-k$ for some $k$ between $1$ and $n$. The sum of the partitioned array sizes equals $n-1$ because pivot itself occupies one element.

As with Cormen et al’s analysis of the quick-sort algorithm, partitioning the input array costs $O(n)$ in run-time. Since Cormen et al are interested in obtaining an upper bound for the run-time and randomized-select only works on one side of the partition, they only need to look at the run time corresponding to the largest of the partitions $T(\max(k-1,n-k)$. Putting this together and attaching an indicator variables $X_k$ to each possible partitioning of the input array gives the bound $$T(n) \leq \sum_{k=1}^{n} X_k . (T(\max(k-1, n-k))+O(n)).$$ The $O(n)$ partitioning overhead occurs regardless of the pivot location, so Cormen et al pull it out of the summation in the second line you wrote down.

Note that Cormen et al could also have worked with the previous equation, with the $O(n)$ cost still attached to the indicator random variables. When determining the expectation, there would then be a term $E[ \sum_{k=1}^{n} X_k O(n)].$ In this application, this term would just come out to be $$\sum_{k=1}^{n} E[X_kO(n)] = O(n)\sum_{k=1}^{n} E[X_k]=O(n)\sum_{k=1}^{n} 1/n=O(n).$$

Mark Yasuda
  • 1,438