0
$\begingroup$

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.

$\endgroup$
2
  • $\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, 2017 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$ Nov 20, 2017 at 11:21

2 Answers 2

2
$\begingroup$

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$.

$\endgroup$
2
  • $\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, 2017 at 13:05
  • $\begingroup$ I edited my answer to add more details. $\endgroup$
    – Shahriaroo
    Nov 21, 2017 at 5:54
0
$\begingroup$

For fixed k, and n ≤ k, O(n) is meaningless. O(n) requires arbitrary large values n. With a fixed k, sorting n ≤ k items with InsertionSort takes O(1) - but with a large constant if k is large. Here's what you do to find the best k:

Iterate for k = 2, 3, 4, 5 ... (hoping that your algorithm is clever enough not to sort arrays of size 1). Create a million or a billion arrays of size k filled with random array elements. Measure how long it takes to sort these arrays using InsertionSort, or another method that you like, and how long it takes to sort these arrays doing one partition step, then sorting both halves with InsertionSort.

Make sure that you don't switch between both methods for each array, because looking at the same data repeatedly will cache the data, and the second operation will tend to be faster.

If your array doesn't contain primitive data but objects with constructors and destructors, you can save a lot more time by reducing the number of assignments. Selection sort will tend to be faster in that case than InsertionSort because it does fewer expensive assignments.

$\endgroup$

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.