UTpaper

Free mock tests & test series

Question 110Asked in DSSSB TGT Computer Science, 25 Jun 2023, Shift 3 (4:30 PM)

The time complexity of a quick soft algorithm which makes use of a median, found by an O(n) algorithm, as pivot element is:

  1. AO(n³)
  2. BO(n log n)
  3. CO(n²)
  4. DO(n)
Show answerHide answer

Correct answer: (B) O(n log n)

Explanation

If the median is used as pivot, every split is exactly balanced: T(n) = 2T(n/2) + O(n), which gives O(n log n) even in the worst case.

From DSSSB TGT Computer Science PYQ, 25 Jun 2023, Shift 3 (4:30 PM)

This is question 110 of DSSSB TGT Computer Science PYQ, 25 Jun 2023, Shift 3 (4:30 PM). See all questions of this paper with answers, or attempt the paper as a timed online test to get your score and all-India rank.