Quicksort on Decreasing Array

Computer Science Level 1

What is the run time of quicksort on array $A$ that is in decreasing order:

$A = [6,5,4,3,2,1,0]?$

O(n)

O(n^2)

O(\log n)

O(n \log n)

1 solution

Karleigh Moore
Mar 23, 2016

Each division (partition) step reduces the problem size by one element. Therefore, each recursive call divides the array into two subarrays of sizes 0 and $n-1$ , and then sorting those arrays into subarrays creates arrays of size 0 and $n-2$ and so on.

The recurrence for this is:

$T(n) = T(0) + T(n-1) + O(n) = T(n-1) + O(n )$

The solution to this recurrence, which we can find using the Master Theorem , is $O(n^2)$

without tell you how to select a pivot, how can we know whats the time it will consume?

dau michael - 2 years, 9 months ago

The question just assume the pivot is the first of the array?

Joe Luo - 2 years, 4 months ago

The problem does not state the use of a random element as the pivot or the use of a median-finding algorithm as the median-of-three. So i think it is asumming that the logical choose are the first or the last element of the array. This causes the worst-case scenario.

Diego Armando Mondragon Robledo - 2 years, 1 month ago

Quicksort on Decreasing Array

1 solution

2 pending reports

Vote up reports you agree with