UTpaper

Free mock tests & test series

Question 30Asked in BEL PE Computer Science, 20 Dec 2025 (5:00 PM)

During the design and analysis process of an algorithm to find the kth smallest element in an unsorted array, a researcher proposes using a modified…

During the design and analysis process of an algorithm to find the kth smallest element in an unsorted array, a researcher proposes using a modified divide-and-conquer approach that always divides the array into five nearly equal parts, recursively selects the median of each part, and then finds the median of those medians to use as a pivot for partitioning. Which of the following best describes the time complexity and design implication of this algorithm?
  1. AO(n); because the median-of-medians approach ensures balanced partitions and linear-time selection.
  2. BO(n log n); because the algorithm behaves like mergesort.
  3. CO(log n); because the recursion depth reduces logarithmically.
  4. DO(n²); because repeated partitioning leads to quadratic comparisons.
Show answerHide answer

Correct answer: (A) O(n); because the median-of-medians approach ensures balanced partitions and linear-time selection.

From BEL PE Computer Science PYQ, 20 Dec 2025 (5:00 PM)

This is question 30 of BEL PE Computer Science PYQ, 20 Dec 2025 (5:00 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.