Here is the question

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)$?

  • $\begingroup$ From pevel 1 to level 2 is $n-1$ $\endgroup$
    – nir shahar
    Jun 14 at 10:00
  • $\begingroup$ Please credit the original source of all copied material. $\endgroup$
    – 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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.