Let 𝐹(𝑛) denote the maximum number of comparisons made while searching for an entry in a sorted array of…

Question

Let 𝐹(𝑛) denote the maximum number of comparisons made while searching for an entry in a sorted array of size 𝑛 using binary search. Which ONE of the following options is TRUE?

Accepted Answer

Correct answer: A — Answer: The correct recurrence for the worst-case number of comparisons in binary search is F(n) = F(floor(n/2)) + 1. Base cases: F(0) = 0 (no elements to check) and F(1) = 1 (one comparison). Recurrence derivation: At each step binary search compares the middle element (counts as 1) and then continues searching in at most floor(n/2) remaining elements. Hence for n ≥ 2, F(n) = F(floor(n/2)) + 1. Closed form: Repeatedly halving n until it becomes 1 takes floor(log2 n) steps, and each step contributes one comparison. Including the final comparison gives F(n) = floor(log2 n) + 1. Therefore the provided recurrence is correct, and the worst-case number of comparisons grows as Θ(log n).

Answer

A. 𝐹(𝑛) = 𝐹(⌊𝑛/2⌋) + 1

Answer

B. 𝐹(𝑛) = 𝐹(⌊𝑛/2⌋) + 𝐹(⌈𝑛/2⌉)

Answer

C. 𝐹(𝑛) = 𝐹(⌊𝑛/2⌋)

Answer

D. 𝐹(𝑛) = 𝐹(𝑛 − 1) + 1

Let 𝐹(𝑛) denote the maximum number of comparisons made while searching for…