What happens to Randomized select algorithm running time if we change line 8 in the code from q-1 to q in CLRS book page 216 ?

what I found is that algorithm should still work and there shouldn't be any change in running time since it depends only on RANDOMIZED PARTITION subroutine. Is it true ?

Randomized-Select (A,p,r,i)
// Finds the ith smallest value in A[p .. r].
if (p = r)
    return A[p]
q = Randomized-Partition(A,p,r)
k = q-p+1   // k = size of low side + 1 (pivot)
if (i = k)
    return A[q]
else if (i<k)
    return Randomized-Select(A,p,q-1,i)
    return Randomized-Select(A,q+1,r,i-k)
  • 1
    $\begingroup$ CLRS book? What might that be? There are quite a few books in the world. $\endgroup$ – copper.hat Feb 1 '18 at 19:52
  • $\begingroup$ Cormen, Leiserson , Rivest , Stein book about Introduction to algorithms - third edition $\endgroup$ – user527248 Feb 1 '18 at 19:54
  • $\begingroup$ here is the link if you need book pdf : ressources.unisciel.fr/algoprog/s00aaroot/aa00module1/res/… $\endgroup$ – user527248 Feb 1 '18 at 19:55
  • 1
    $\begingroup$ the return Randomized-Select(A,p,q-1,i) part is now return Randomized-Select(A,p,q,i) after the change $\endgroup$ – user527248 Feb 1 '18 at 20:22

The running of Randomized-Select (worst case) is $\Theta(n^2)$ after changing q-1 to q since the running time of Randomized-Partition is $\Theta(n+1)$ = $\Theta(n)$, the expected running time remain the same too.

But the algorithm will use more space after the change if we didn't use arrays.

  • $\begingroup$ doesn't it in the worst case go to infinite loop ? $\endgroup$ – user527248 Feb 1 '18 at 21:21
  • $\begingroup$ I have an implementation of that algorithm in C++ and tested after changing q-1 to q and it worked. $\endgroup$ – edcharlie Feb 2 '18 at 21:24

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.