Author: Stan Eisenstat
Subject: Re: [Cs223] Hwk4 Note C5
Date: Saturday, 28 Mar 2020, 14:33:28

    > Message Posted By: Unknown
    >
    >     > Message Posted By: Stan Eisenstat
    >     >
    >     > C is the constant in the bound of the form C * #compares + N
    >     > that you are trying to achieve.  For example, for Test #303
    >     > the value of C is 4; for Test #304 the value is 2.
    >
    > What determines the value of C? Is it arbitrary?

Qsort can only pass Test #303 if the number of calls
from quickSort does not exceed 4 * #compares + N.

Qsort can only pass Test #304 if the number of calls
from quickSort does not exceed 2 * #compares + N, which
is a more stringent test.

Although I have not implemented it yet (and thus could
be mistaken), there is an algorithm that needs only
1 * #compares + N calls, which is learly optimal.

--Stan-