1
$\begingroup$

I am learning the Quicksort algorithm and I am struggling with understanding the time complexity.

Here is the JavaScript ES6 code for the partition function that is used in the algorithm:

let partition = function(arr, low, high) {
  let pivotValue = arr[low];
  let i = low;
  let j = high;

  while (i < j) {
    while (i <= high && arr[i] <= pivotValue) {
      i++;
    }

    while (arr[j] > pivotValue) {
      j--;
    }

    if (i < j) {
      // swap arr[i], arr[j]
      let temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    } 
  }

  arr[low] = arr[j];
  arr[j] = pivotValue;

  return j;
};

I read that there is n work done for a single invocation of the partition function because there is n - 1 work being done in the while loop and 1 unit of work being done when copying the pivot back.

I don't understand why there is n - 1 work done in the while loop. As per my understanding, every time you make a comparison between the array value and pivotValue (arr[i] <= pivotValue or arr[j] > pivotValue), that is a unit of work being done.

So aren't there actually n units of work being done in the while loop, for a total of n + 1 in the partition function?

$\endgroup$
  • $\begingroup$ I have never seen a definition of "unit of work", and that's definitely not a standard concept. Are you counting comparisons by any chance? $\endgroup$ – Yuval Filmus Jun 9 at 18:58
  • $\begingroup$ Moreover, the difference between $n-1$, $n$ and $n+1$ is usually highly unimportant when determining the asymptotic time complexity of a function. $\endgroup$ – Yuval Filmus Jun 9 at 18:59
  • $\begingroup$ @YuvalFilmus, yes, I am counting the comparisons. For reference, I am following the notes provided on Emory University's page if they are of any use: mathcs.emory.edu/~cheung/Courses/171/Syllabus/7-Sort/… (towards the bottom) $\endgroup$ – Nick Nemtcev Jun 9 at 19:14
  • $\begingroup$ Just saying: This implementation has two fatal flaws: One, it will result in a total of O (n^2) comparisons if an array is already sorted; this is very easily fixed. Two, it will result in O (n^2) comparisons if all array elements are equal, which is much harder to fix. $\endgroup$ – gnasher729 Jun 9 at 21:54
  • $\begingroup$ Just saying: The first problem is not that easily fixed. If you want to pick something other than the first element as the pivot, you'll have to think very, very hard about the last swap. I hope everyone reading the code takes a very, very hard look at the last two lines. I'd want very good comments in the code explaining why they are correct, otherwise I'd find the code unacceptable. $\endgroup$ – gnasher729 Jun 9 at 22:07
1
$\begingroup$

The number of "work" being done, should be counted with the big-O notation. This means - that you count the while loop as $O(n)$ and any other constant work done (for example, the work after the while) is $O(1)$ and $O(n)+O(1)=O(n)$ so it wont make a difference.

Counting the "work" without big-O is not well-defined in the general case - so you should avoid it altogether

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You can of course count "number of comparisons between array elements", and then the result is well-defined. $\endgroup$ – gnasher729 Jun 9 at 21:55
  • $\begingroup$ Yes of course. But this would not define time complexity in the broader manner. $\endgroup$ – nir shahar Jun 9 at 21:57

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.