Consider this algorithm:

1 if p == r
2  return A[p]
4 k = q - p + 1
5 if i == k // the pivot value is the answer
6  return A[q]
7 elseif i < k
8  return RANDOMIZED-SELECT(A, p, q - 1, i)
9 else return RANDOMIZED-SELECT(A, q + 1, r, i - k)

The book CLRS claims that if we set $T(n)$ to be the running time of the algorithm on an input $A$ of size $n$, then $T$ is a random variable. However, I think it's not since if we define $\Omega$ to be the set of all inputs of all sizes $n$ and set $\mathcal{F}$ as $\mathcal{P}(\Omega)$ and let $T$ to be a function from $\Omega$ to $\mathbb{R}$, if $n = m$ then it doesn't follow that $T(n) = T(m)$ since the algorithm might have different running times on arbitrary inputs of the same size. Also note that the algorithm is randomized. So why does it say that $T$ is a random variable?


I'm not sure I understand your counterargument but look at it like this:

For given $n$ define $\Omega_n$ to be all inputs of size $n$ and $\mathcal{F_n} = \mathcal{P}(\Omega_n)$.

Let $(T_{n})_{n\in\mathbb{N}}$ be a sequence of functions:

$$T_{n} : \Omega_n \rightarrow \mathbb{R}$$

Clearly $\forall t,n. \{\omega \mid T_{n}( \omega) \leq t \} \in \mathcal{F_n}$, which shows that $\forall n. T_{n}$ is a random variable on $\Omega_n$.

  • $\begingroup$ Of course we don't need the $T(n, \omega)$ part. Actually, we need to show for any $A$ it's true that $T_{n}^{-1} (A) \in \mathcal{F}_{n}$ which is obvious but the argument is true. $\endgroup$
    – Emad
    Jul 27 '21 at 9:54
  • $\begingroup$ @Emad This is the usual definition of a random variable. Please see en.wikipedia.org/wiki/… $\endgroup$
    – idmean
    Jul 27 '21 at 9:58
  • $\begingroup$ I see. They're equivalent $\endgroup$
    – Emad
    Jul 27 '21 at 10:08

Our input is specific, but the input maybe have different permutations, so we can't claim that $T$ is a function that map set of all inputs to $\mathbb{R}$. But i think, it's true that we look at $T$ as a function that map a input to a permutation, formally, let $X$ be the input of size $n$, and denote $\mathfrak S_n$ be the group of the permutations of $X$ : $$ T:X\to \mathfrak S_n. $$ So $T$ is a random variable that map input $X$ of size $n$ to $\mathfrak S_n$.

  • 1
    $\begingroup$ Since $T$ must be the running time I think we can't define it that way. However, if we compose this function with another function mapping each element of $S_{n}$ to its running time and consider the sequence of such composed functions, then it's something. $\endgroup$
    – Emad
    Jul 27 '21 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.