更改随机选择算法对运行时间的影响

Question

如果我们将CLRS书第216页的代码中的第8行从q-1更改为q，随机选择算法的运行时间会怎样？

我发现的是，算法应该仍然有效，并且运行时间不应有任何变化，因为它仅取决于RANDOMIZED PARTITION子例程。是真的吗？

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)

Answer 1

第I个统计信息可能位于：左部分范围p ..q-1右侧部分-范围q + 1..r恰好在索引q