Question

What is the time complexity of the above recursive implementation of binary search?

(a) O(n)

(b) O(2^n)

(c) O(logn)

(d) O(n!)

I had been asked this question by my college professor while I was bunking the class.

My question is from Search an Element in an Array using Recursion topic in chapter Recursion of Data Structures & Algorithms II

Answer 1

Right answer is (c) O(logn)

The best I can explain: The time complexity of the above recursive implementation of binary search is O(logn).