# Randomized select analysis of running time if we change one line of code

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)
else
return Randomized-Select(A,q+1,r,i-k)

• CLRS book? What might that be? There are quite a few books in the world. – copper.hat Feb 1 '18 at 19:52
• Cormen, Leiserson , Rivest , Stein book about Introduction to algorithms - third edition – user527248 Feb 1 '18 at 19:54
• here is the link if you need book pdf : ressources.unisciel.fr/algoprog/s00aaroot/aa00module1/res/… – user527248 Feb 1 '18 at 19:55
• the return Randomized-Select(A,p,q-1,i) part is now return Randomized-Select(A,p,q,i) after the change – 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.