CODEWITHSUNDEEP
big-otime-complexityquicksort
Master
Master

Reputation: 41

Best case of quick sort variation

Say you have this kind of quick-sort implementation, which is probably a little bit different than the standard one:

qsort(list):
if list is of length 1 or lower - 
     return list
else - 
     choose a random pivot 
     smaller - get all elements that are smaller than the pivot
     equal - get all elements that are equal to the pivot, including the pivot itself
     greater - get all elements that are greater than the pivot
     return qsort(smaller) + equal + qsort(greater)

Wouldn't the best case scenario for that function be when the function receives a list in which all elements are the same, and in that case, the best case time complexity would be O(n), which is better than the best case time complexity of the standard version of quick-sort, which is O(n log n)?

The reasoning for that is that the function only creates those partitions once, as smaller and greater lists would be empty (as all of the elements are the same), and this would end the recursion, as qsort(smaller) and qsort(greater) would just return the empty lists.

Is that correct?

Upvotes: 0

Views: 577

Answers (1)

DrYap
DrYap

Reputation: 6647

Yes, in the case you describe the time complexity will be O(n).

However, the space will also be O(n) as a new list equal needs to be created. This is worse that qsort which sorts in place so has an O(1) (constant) space requirement.

The qsort time complexity of O(n lg(n)) is an average case which is calculated assuming statistically random data. Your adaptation will help performance in the edge case that all the values are equal which is very unlikely (although you might have prior knowledge about the data which makes it more likely).

If you were considering using this algorithm as opposed to the standard qsort I would recommend against it. Since use of extra lists adds overhead in the adding of elements and concatenation (where this overhead is depends on the implementation of the list). This overhead is not present in qsort since it sorts in place.

Upvotes: 1

Related Questions