The recurrence relation that arises in relation with the complexity of binary…

2017

The recurrence relation that arises in relation with the complexity of binary search is:

  1. A.

    T(n) = 2T(n/ 2) + k , where k is constant

  2. B.

    T(n) = T(n / 2) + k , where k is constant

  3. C.

    T(n) = T(n / 2) + log n

  4. D.

    T(n) = T(n / 2) + n

Attempted by 161 students.

Show answer & explanation

Correct answer: B

Binary search divides the problem into one subproblem of size n/2 with constant work per step, leading to T(n) = T(n/2) + k.

Explore the full course: Isro