Author: Stan Eisenstat
Subject: Re: [Cs223] 2 * # of compares + N constraint in walk-through
Date: Tuesday, 17 Mar 2020, 17:16:49

    > Message Posted By: Unknown
    >
    > According to the walkthrough, 2 * (# of compares) is equivalent to M where
    > M is the number of elements being partitioned in the call.

This is incorrect, as follows from several earlier
postings.

The number of calls to addD() and push() should be at
most 2 * (# of compares) + N, which can be achieved by
calling addD() and pushD() at most 2*(M-1)+1 times (not
including calls when quickSort calls itself recursively).
See Note C, Point 5.
=====

    > When doing the partition step in a quicksort of a set of N items, doesn't
    > that take N-1 number of compares as we have to compare every element
    > besides the pivot to the pivot? Shouldn't 2 * (# of compares) actually be
    > 2 * (M-1) instead of simply M as stated in the walkthrough?

It should be 2*M-1, which is equivalent to the 2*(M-1)+1
above.

--Stan-