Time complexity of quicksort for arrays in increasing or descreasing order

Question

Two $n$-size arays are given: $n_1$ is in decreasing order and $n_2$ is in increasing order.

Let $c_1$ be the time complexity for $n_1$ using quicksort, and $c_2$ the time complexity for $n_2$ using quicksort.

I think $c_1 = c_2$ and $c_1=O(n^2)$? Is this correct ?

I am using the last element as a pivot for each partition.

gnasher729 · Answer

Quicksort is just an idea. There are algorithms and implementations.

Only stupid implementations will run in O(n^2) for sorted or reversed sorted arrays. Good sorting implementations actually check for elements in ascending or descending order at the beginning and end of the array and will handle either case in O(n), because wanting an array sorted without checking that it is sorted before is such a common case. Such implementations will fall back on Quicksort for handling the more difficult parts.

(It’s not just sorted arrays. You can have a general algorithm that sorts the concatenation of two sorted arrays in O(n), or a sorted array with fewer than O(n / log n) random elements added, or a sorted element with one random element changed).

Time complexity of quicksort for arrays in increasing or descreasing order

One Answer

Add your own answers!

Ask a Question