1
$\begingroup$

Question: Suppose we have the following array where we want to find the smallest $i$th smallest element in the array using QuickFind algorithm (similar to QuickSort):

enter image description here

$$ QuickFind\left( A,n,i \right) =\left\{ \begin{array}{l} QuickFind\left( A,k-1,i \right) ,\ i<k\\ QuickFind\left( A,n-k,k-i \right) ,\ i>k\\ x,\ i=k\\ \end{array} \right. $$

Now, we can see that we don't know which part is larger the left part where $<x$ or the right part where elements are greater than $>x$. So, what we do in this case is to take the largest of the two subprblems:

$$T(n) = max\{T(k-1), T(n-k)\} \tag{1}\label{1}$$

Problem: why we take the max of two subproblems? If $i<k$, then we simply take the left part, otherwise $i>k$ we take the right part of $x$ at the $k$th element. So, why please taking the max of 2 recursions and what does even mean?

Problem 2: then to calculate the expected position of $k$,

$$E[T(n)] = \sum_{j=1}^{n}(Pr(k=j))E\left[ max\{T(j-1), T(n-j)\}\right] \tag{2}\label{2}$$

Also, adding to problem 2, can you please show how we get \ref{2}? I know that $E[X] = \Sigma_i x_i \times p(x_i)$, so what quantities in \ref{2} corresponds to equation of expectation $E[X]$? From what I see, \ref{2} should be written if we treated $T(n)$ as a random variable that takes several values based on \ref{1}, so we should have it without $E[\cdot]$ around $ max\{T(j-1), T(n-j)\}$

$$E[T(n)] = \sum_{j=1}^{n}Pr(k \in T(n) = j) \times max\{T(j-1), T(n-j)\} \tag{3}\label{3}$$

what do you think please about how I rewrote \ref{2}? Also should it based on expectation definition to have $Pr(X=x_i)$ corresponds to $Pr(k \in T(n) = j)$ as this is how I interpreted $Pr(k=j)$, so what you think please?

Edit: I just look for please to understand $T(n)$ rule above and nothing more. Since QuickFind is given recursively, so what is the point of taking max of $T(n)$ as defined above in \ref{1} please? The justification I got was the one we should put into the recursion of $T(n)$ is because we don't know whether our element will be on the left or on the right, so we take $max$ of the two subproblems. So again, how we don't know if the ith smallest element is on the left on right given we can compare with $x$ at kth position to help us whether to go left or righ, why max $T(n)$?

$\endgroup$
2
  • 1
    $\begingroup$ What is $T$ here? $\endgroup$
    – nir shahar
    Oct 1, 2021 at 15:27
  • $\begingroup$ @nirshahar. Thanks . $\endgroup$
    – Avv
    Oct 1, 2021 at 15:30

1 Answer 1

1
$\begingroup$

I assume $T(n)$ represents the run-time for an input of size $n$.

Problem 1

You are right that if $i<k$ then we take the left part, and if $k<i$ then the right one. However, creating a recurrence relation with this way of choosing the subproblem size can be problematic - we don't know beforehand which part we will need to choose, so we can't solve the equation.

To solve this problem, we consider only giving a bound on $T(n)$ rather than getting the exact solution. So, if we could either take the left subproblem or the right one, we either case perform at most as the maximum between them.

Hence, we can write a simpler recurrence relation in the form of $T(n)\le \max\{T(k-1),T(n-k)\}$. This relation might be simpler to solve now, and gives a bound on the run-time of the algorithm.

Problem 2

As you have said, $T(n)$ can be thought of as a random variable. Therefore, $\max\{T(j-1),T(n-j)\}$ will also be a random variable, and that should be a big red flag in equation $3$ - since an expected value must always be a real number (or infinite). The expected value is simply never a random variable.

You can derive equation $2$ without all the expected values - from the complete probability theorem. Then, apply the expected value on both sides and use its linearity properties.

Now, as we didn't directly use the definition of expectation to get equation $2$, the term $\Pr[k=j]$ should make more sense to you now.

$\endgroup$
9
  • $\begingroup$ I.e in that part that is max (as we take the max of two parts in $T(n)$) please? I see you are saying it's just an approximate, so by taking larger part, it's meant the part that has more elements or size? But what if the element is not that part please? Once the maximum size is chosen, the other part won't be chosen once we roll back to first caller function? So it will be lost in this way you and the solution I presented are following? $\endgroup$
    – Avv
    Oct 1, 2021 at 17:06
  • $\begingroup$ Also, nir, can you please show how we get \ref{2}? I know that $E[X] = \Sigma_i x_i \times p(x_i)$, so what quantities in \ref{2} corresponds to equation of expectation $E[X] $ $\endgroup$
    – Avv
    Oct 1, 2021 at 17:16
  • $\begingroup$ I added another part under problem 2. $\endgroup$
    – Avv
    Oct 1, 2021 at 17:36
  • 1
    $\begingroup$ They don't know, and don't need to know. Since we are taking the $\max$ on both cases, we will always "pay" more than both of the cases. The idea here is that we utilize the fact that $a,b\le \max{a,b}$, so if we have some $x\in \{a,b\}$ (it is either $a$ or $b$ but we don't know which), we still know that $x\le \max\{a,b\}$. $\endgroup$
    – nir shahar
    Oct 1, 2021 at 17:37
  • 1
    $\begingroup$ @Avra I updated the answer, take a look at it again. $\endgroup$
    – nir shahar
    Oct 1, 2021 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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