Number of comparisons in Quicksort

So would it be correct to say that the number of comparisons from level 1 to level 2 would be $$2(n/2-1)$$?

Or would it be more correct to say that the number of comparisons is $$2^i(n/2^i-1)$$?

• From pevel 1 to level 2 is $n-1$ Jun 14 at 10:00
• Please credit the original source of all copied material.
– D.W.
Jun 14 at 20:55

Splitting the list entails comparing every element in the current list with the pivot. That is, if the list is of size $$n$$, you would have $$n-1$$ comparisons.
Then, the list is split into sizes $$|B|$$ and $$|S|$$ and continues recursively. On the $$B$$ part you will choose a pivot and make $$|B|-1$$ comparisons to split them into two (sub)lists. Same with $$S$$. This continues until you get list of size $$1$$, for which you computes $$C(1)$$.