Let $P$ be a quicksort program to sort numbers in ascending order. Let…

PYQ GATE 1987Modified — slightly modified from the official paper; see the solution

Let $P$ be a quicksort program to sort numbers in ascending order. Let $t_{1}$ and $t_{2}$ be the time taken by the program for the inputs $\left[1 \ 2 \ 3 \ 4\right]$ and $\left[5 \ 4 \ 3 \ 2 \ 1\right]$ , respectively. Which of the following holds? Assume each partition chooses the first element as pivot, compares it once with each other element in that partition, and that time is measured by this comparison count.

A.
$t_{1} = t_{2}$
B.
$t_{1} > t_{2}$
C.
$t_{1} < t_{2}$
D.
$t_{1}=t_{2}+5 \log 5$

Attempted by 84 students.

Explore the full course: Algorithms

Let \(P\) be a quicksort program to sort numbers in ascending order. Let…