I learned in my data structures class that QuickSort can be optimized by calling the InsertionSort method when the length of the subarray is less than a certain threshold. However, when it comes to the actual time complexity calculation of the optimized version of QuickSort, I'm having trouble finding the result. The problem is as follows.

An optimized-QuickSort function calls the InsertionSort method instead of itself when the size of the sublist is less than k. Assuming that the time complexity of QuickSort and InsertionSort is $c_1n\log n$, $c_2n^2$ respectively, what is the time complexity of optimized-QuickSort? (Calculate for the average case)

I assumed that the sublist is split into 1:1 by each step. As a result, I got $c_1nlog$($n\over k$) + $c_2nk$, but I am definitely not sure of my answer since I don't know if my assumption is correct. In the textbook, the average case of a non-optimized QuickSort was supposed to be calculated by assuming the partition could be the first element, second element, third element, ... , last element and then dividing the whole sum by n.

I would appreciate some help! Thanks.

  • $\begingroup$ "However, when it comes to the actual time complexity calculation of the optimized version of QuickSort, I'm having trouble finding the result." -- that's not a suprise! Changing the algorithm for finitely many inputs doesn't change it's "complexity" (a horrible misnomer), if you mean "the $\Theta$-class of the running-time cost function" by that. $\endgroup$ – Raphael Nov 20 '17 at 11:12
  • $\begingroup$ The optimisation with the InsertionSort is not going to change your time complexity since it will not change the structure of the asymptotic recurrence you will need to derive for the average case. Put another way, this optimisation kicks in only for a finite number of cases that are effectively considerable as base cases for the overall QuickSort Recurrence $\endgroup$ – LastIronStar Nov 20 '17 at 11:21

The height of tree is not $log(\frac{k}{n})$ which is negative because $k<n$. We stop expanding the tree when we reach $k$, therefore we reduce the height of the original tree by $log(k)$. So the height is $log(n)-log(k)=log(\frac{n}{k})$ and the average running time will be: $$c_1nlog(\frac{n}{k})+c_2nk=c_1nlogn-c_1nlogk+c_2nk$$ As noted in comments, since $k$ is constant, that is equivalent to $\theta(nlogn)$.

EDIT: I just noted that the problem was about average case complexity and you assumed the partition to have 1:1 ratio, which is the assumption for best case scenario. For average case analysis, we shouldn't consider any fixed partition ratio.

You can use the average case analysis in section 7.4.2 of CLRS book; except that here the probability of comparing the ith and jth element would be at most $\frac{1}{j-i+1}$, so the $c_1nlogn$ would be an upper bound on the Quicksort part of the average case. As for Insertion sort part, there would be at most $n/k$ leaves with size $k$, with total cost of $\frac{n}{k}c_2k^2=c_2nk$.

  • $\begingroup$ Oh sorry I wrote it wrong. Thanks for telling me that! I fixed it. But could you explain a little bit more specifically how you got the $c_2nk$ though? $\endgroup$ – Zack D Nov 20 '17 at 13:05
  • $\begingroup$ I edited my answer to add more details. $\endgroup$ – Amir H Nov 21 '17 at 5:54

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.