How to get the optimized quicksort algorithm's time complexity

Question

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.

Answer 1

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