edited by
1,873 views
0 votes
0 votes

Consider a scenario of modified quick sort, where we have given an input sorted array A[1 . . . n], all elements of array are distinct and n ≥ 3. Pivot is the median of set of 3 elements [First element, middle element, and last element]. What will be worst case time complexity of modified quick sort?

  • Ο(n2)
  • Ο(n logn)
  • Ο(n2 logn)
  • Ο(n log log n)

I think it will be B but they have given as A....???

edited by

1 Answer

0 votes
0 votes

The correct answer is B.

Median of 'n' elements in a sorted array is the n/2 th element which falls exactly at the n/2 th position. Thus, dividing the array approximately in two equal halves.

Since, no complexity is given to find the median we will consider constant time.
Now, The recursive equation for this problem becomes:

$T(n) =O(1) + O(n) + T(n/2) + T(n/2)$

where O(1) is the complexity to find median in every recursive call.

Solve using Recursive tree method or Master's Theorem  : $O(nlogn)$

:)

edited by

Related questions

0 votes
0 votes
1 answer
1
LavTheRawkstar asked Jan 12, 2017
808 views
INSERTION-SORT (A, n) ⊳ A[1 . . n]for (j ← 2 to len(A) ){key ← A[ j];i ← j – 1 ; while (i 0 and A[i] key) { A[...
1 votes
1 votes
2 answers
4
vishal chugh asked Jan 24, 2018
1,734 views
What is the worst case time complexity to find kth smallest element into an array of ‘n’ element?