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)
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.