Explore BrainMass
Share

Explore BrainMass

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

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

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

    © BrainMass Inc. brainmass.com June 1, 2020, 4:36 pm ad1c9bdddf
    https://brainmass.com/computer-science/algorithms/quicksort-maximum-of-q-2-n-q-1-2-104163

    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

    ADVERTISEMENT