Question

11

QUESTION 11 What is the runtime of Binary Search? a. O(n) b. Onlogn) c. Of(logn)) d. Odlogn)

Answer 1

Answer : d. O(log n)

Lets eloberate this , Binary search performed on sorted array and the sorted array is divided into half repeatedly. We will search for the value in the left half if the value is less than middle element or on the right half if searching value is greater than middle value. If the value is less than middle element then left half will be divided into two halfs...After every iteration the length of the searching space id going to be reduced .

At first iteration length  of the array is n

At second iteration length of the array is n/2

At third iteration length of the array is n/2² (n/4 )

At fourth iteration length of the array is n/2³ (n/8)

After  kth iteration length of the array is n/2^k

after k divisions length of the array is 1

lets put this into equation ...

n/2^k = 1

n = 2^k

log₂(n) = log₂(2^k) ----->after appliying log on both sides

log₂(n) = k log₂(2) ----> log_a(a) = 1

k = log₂(n)