c < min(k,q)

Next: Up: Correctness Proof Previous: Correctness Proof

c < min(k,q)

In this situation we have

$\begin{displaymath} P'_{3}[i] = P_{2}[i] \quad (i \leq c) \end{displaymath}$

P'₃[c+1] = y_c+1 > x_c+1 = P₂[c+1]

So P'₃ > P₂

Timothy Lewis
11/12/1997