Question
Data Science and Artificial Intelligence Question on Binary Operations
Let F(n) denote the maximum number of comparisons made while searching for an entry in a sorted array of size n using binary search.
Which ONE of the following options is TRUE ?
A
F(n) = F(⌊n/2⌋) + 1
B
F(n) = F(⌊n/2⌋) + F(⌈n/2⌉)
C
F(n) = F(⌊n/2⌋)
D
F(n) = F(n - 1) + 1
Answer
F(n) = F(⌊n/2⌋) + 1
Explanation
Solution
The correct option is (A) : F(n) = F(⌊n/2⌋) + 1.