script

Wednesday, February 27, 2013

9.2-2


Argue that the indicator random variable $X_k$ and the value $T(max(k - 1, n - k))$ are independent.
$X_k$ and $T(max(k - 1, n - k))$ are independent. Because $X_k$(sub array A[p..q] has exactly k elements k=1..n) is dependent on random choice made by the random-partition call and $T(max(k - 1, n - k))$ is making its own random choices because it is a different recursive call. Hence they are independent.

No comments:

Post a Comment