What is the time complexity of binary search with iteration?
2025
What is the time complexity of binary search with iteration?
Answer: B. O(logn) — Answer: b Explanation: In binary search, the problem size is halved at each step. This gives the recurrence relation T(n) = T(n/2) + O(1), where O(1)…
- A.
O(nlogn)
- B.
O(logn)
- C.
O(n)
- D.
O(n2)
Attempted by 350 students.
Show answer & explanation
Correct answer: B
Answer: b
Explanation: In binary search, the problem size is halved at each step. This gives the recurrence relation T(n) = T(n/2) + O(1), where O(1) represents the constant time to compare the middle element.
Step 1: Start with a sorted array of size n.
Step 2: Compare the target value with the middle element.
Step 3: If the target is found, return the index. Otherwise, discard half of the array and repeat.
Step 4: The number of times we can divide n by 2 until we reach 1 is log₂n. Therefore, the time complexity is O(logn).