Share
Explore BrainMass

Quicksort : Maximum of "q^2 + (n-q-1)^2"

Show that "q^2 + (n-q-1)^2" achieves a maximum over q = 0, 1, ..., n-1 when q = 0 or q = n-1.

Solution Preview

Let us expand and reorganize the terms of the given equation -

q^2 + (n-q-1)^2
= q^2 + {(n-1) - q}^2
= q^2 + (n-1)^2 + q^2 - 2(n-1)q
= (n-1)^2 + 2(q^2) - 2(n-1)q
= (n-1)^2 - 2q{(n-1)-q}

Now first term is a positive ...

Solution Summary

Solution first rewrites the given equation to separate the terms involving q.

$2.19