# Can quick sort time complexity be $\Theta(n\sqrt n)$ for some inputs?

I know that the time complexity of quick sort in the worst case is $\Theta(n^2)$ and in the average case is $\Theta(n \log n)$. Can it be $\Theta(n\sqrt n)$ for certain inputs?

• In the average case it's $\Theta(n\log n)$. It can probably be $\Theta(n\sqrt{n})$ for certain inputs of a certain structure. I suggest looking up the best and worst cases for quicksort, and trying to combine them. – Yuval Filmus Feb 7 '18 at 13:08

Assume the array is sorted. If you always pick the element at n/2 as pivot then the time is O(n log n). If you always pick the first or last element it’s $O(n^2)$.
So which pivot gives you $O(n^{1.5})$?
• This answer is very much incomplete. And misleading too, for any constant $c$, if you always pick the element at $cn$ as your pivot the complexity is $\Theta(n \log n)$, and never $\Theta(n\sqrt n)$. – orlp Sep 28 '19 at 8:17