UTpaper

Free mock tests & test series

Question 55

Which of the following is correct recurrence relation for worst caset of binary search?

  1. AT(n) = 2T(n/2) + O(1), T(1) = T(0) = O(1)
  2. BT(n) = T(n/2) + O(n), T(1) = T(0) = O(1)
  3. CT(n) = T(n/2) + O(1), T(1) = T(0) = O(1)
  4. DT(n) = T(n/2) + O(log n), T(1) = T(0) = O(1)
Show answerHide answer

Correct answer: (C) T(n) = T(n/2) + O(1), T(1) = T(0) = O(1)

Explanation

Each binary search step does a constant amount of work and continues in one half of the array, giving T(n) = T(n/2) + O(1), which solves to O(log n).

From DSSSB TGT Computer Science Practice Set 5

This is question 55 of DSSSB TGT Computer Science Practice Set 5. 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.