Trying to understand the 2N lnN compares for quicksort

1. It seems that N+1 as the number of comparisons for the partition step is an error in the book. You need to find out for each of the N–1 non-pivot elements whether it is less than or greater than the pivot, which takes one comparison; thus N–1 comparisons in total, not N+1. (Consider the simplest case, N=2, i.e. one pivot and one other element: There is absolutely no room for doing three comparisons between two elements.)

2. Consider the case where the chosen pivot happens to be the smallest element (k=1). This means that the array is divided into an empty part to the left (there are no elements that are less than the pivot) and a part to the right that contains all the elements except for the pivot (all other elements are greater than the pivot). This means that the sub-problems that you now want to solve recursively have sizes 0 and N–1 (k–1 and N–k), respectively, and require C(0) and C(N–1) comparisons; thus, C(0)+C(N–1) in total.

   If the pivot happens to be the second smallest element (k=2), the sub-problem sizes are 1 and N–2 (k–1 and N–k; one element on the left, because it is the only one smaller than the pivot). Thus, recursively solving these sub-problems requires C(1)+C(N–2) comparisons. And so on if the pivot is the third smallest element, the fourth, etc. These are the expressions in the numerators.

   Because the pivot is chosen randomly from among the N elements, each case (pivot is smallest, pivot is second smallest, etc.) occurs with equal probability 1/N. That’s where the N in the denominators comes from.

N + 1 is not an error.  N - 1  compares against the pivot are necessary to examine all array elements. Additional one/two compares come from pointer crossing. There are three cases:

1. Pivot is the largest element:

                                 ⬅ j
                                   ⯆
   ┌───┬───────────────────┬─────┐
   │ p │        < p        │ ≤ p │
   └───┴───────────────────┴─────┘
                              ⯅
                              i
   

   j points past the end of the array. When it's decremented it checks the element pointed to by i one more time. N - 1 + 1 = N compares in total.
2. Pointers cross after advancing i:

                        ⬅ j
                          ⯆
   ┌───┬─────────┬─────┬─────┬────
   │ p │         │ ≤ p │ ≥ p │
   └───┴─────────┴─────┴─────┴────
                    ⯅
                    i ➡
   

   j's element was previously swapped and therefore already examined by i. When i advances (from < after a simple increment or from ≤ after a swap), it examines j's element once again. Then j is decremented and it checks an element previously pointed to by i. These 2 extra compares bring the total to N - 1 + 2 = N + 1.
3. Pointers cross after advancing j:

                        ⬅ j
                          ⯆
   ┌───┬─────────┬─────┬─────┬────
   │ p │   ≤ p   │ ≥ p │ ≥ p │
   └───┴─────────┴─────┴─────┴────
                    ⯅
                    i
   

   j is decremented at least once to check i's element. If i stopped at an element strictly greater than the pivot, j is decremented a second time.

All in all the total number of compares is either N or N + 1. If all elements are distinct, N compares happen only when the pivot is the largest element.

The average number of compares when all elements are distinct is

1       N - 1                   1
─ × N + ───── (N + 1) = N + 1 - ─
N         N                     N

1 / N correction accounts for the (C_{N - 1}, C_0) split (pivot is the largest element) and in the limit N → ∞ it can be ignored.

Actually 1 / N doesn't affect the analysis at all.

              1   2  N-1
C_N = N + 1 - ─ + ─   ∑  C_i
              N   N  i=0

After multiplying by N

                          N-1
N C_N = N (N + 1) - 1 + 2  ∑  C_i
                          i=0

and differencing

N C_N - (N - 1) C_{N - 1} = 2 N + 2 C_{N - 1}

1 / N goes away.