Quick sort algorithm

What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?

• Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)

• Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)

• Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)

• Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)

Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.

• $O\left(n^2\ \log n\right)$
  

• $O\left(n^2\right)$

• $O\left(n\ \log n\ \log n\right)$
  

• $O\left(n\log n\right)$

Let P be a QuickSort Program to sort numbers in ascending order using the first element as pivot. Let t1 and t2 be the number of comparisons made by P for the inputs {1, 2, 3, 4, 5} and {4, 1, 5, 3, 2} respectively. Which one of the following holds?

• t1 = 5

• t1 < t2

• t1 > t2

• t1 = t2

You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

• O(n²)

• O(nLogn)

• Theta(nLogn)

• O(n³)

Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort.

• $O\left(n^2\ \log n\right)$

• $O\left(n^2\right)$

• $O\left(n\ \log n\ \log n\right)$

• $O\left(n\log n\right)$

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?

• $O\left(n\right)$

• $O\left(n\ \log n\right)$

• $O\ \left(n^2\right)$

• $O\ \left(n!\right)$

Quicksort is run on two inputs shown below to sort in ascending order taking first element as pivot,

(i) 1, 2, 3,......., n

(ii) n, n-1, n-2,......, 2, 1

Let C₁ and C₂ be the number of comparisons made for the inputs (i) and (ii) respectively. Then,

• C1 < C2

• C1 > C2

• C1 = C2

• We cannot say anything for arbitrary n

What is recurrence for average case of QuickSort and what is the time complexity in average case?

answer choices

• $O\ \left(n^2\right)$

• $O\ \left(n!\right)$

• $O\ \left(n\ \log\ n\right)$

• $O\ \left(\frac{\left(n^2+n\ \log\ n\right)}{2}\right)$

Partition a list A[] into two non-empty parts.

in left part the values should be:

• A [ ] <= pivot

• A [ ] > pivot

• A[] >= pivot

• A [ ] < pivot

Partition a list A[] into two non-empty parts.

in right part the values should be:

• A [ ] > pivot

• A [ ] >= pivot

• A [ ] < pivot

• A [ ] <= pivot