Author: Stan Eisenstat
Subject: Re: [Cs223] Stats vs. spec
Date: Saturday, 28 Mar 2020, 09:12:16

    > Message Posted By: Unknown
    >
    > In the announcement about Stats.pl, the output reports
    > 2*(#compares+#lines). However, in the pset spec, the required number of
    > calls to add-/pushD() is 2#compares + #lines. Is the calculation in
    > Stats.pl then an incorrect upper bound for the required efficiency of our
    > solution?

As stated in the specification:

  * QsortH will count the number of calls to addD()/pushD().  An EFFICIENT
    implementation requires at most 2*#compares + N calls to addD()/pushdD()
    when the number of items to sort is N > 4.  (This does not include the
    calls to save the lines on a queue or stack as they are read).

Since Stats.pl does not know the source of the calls to
addD() / pushD(), it reports the total number, INCLUDING
the N calls to save the lines on a queue or stack as
they are read.

It reports 2 * (#compares + N) as the limit rather than
2 * #compares + N to make the comparison with the total
number of calls easier.

--Stan-