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

    > Message Posted By: Unknown
    >
    > Note C5 says: "Achieving at most C * #compares + N calls to addD()/pushD()
    > by limiting the number of such calls to at most C*(M-1)+1 when quickSort
    > is sorting M items (the C*(M-1)+1 does not include recursive calls to
    > quickSort)."
    >
    > Is N the total number of items being sorted? What is C?

Yes, N is the total number of items.

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.

--Stan-