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?

Improve this question
$\endgroup$
5
  • $\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$ Commented Jun 9, 2020 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$ Commented Jun 9, 2020 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$ Commented Jun 9, 2020 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$ Commented Jun 9, 2020 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$ Commented Jun 9, 2020 at 22:07

1 Answer 1

Reset to default
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

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.