GATE Overflow Test Series | Algorithms | Test 1 | Question: 21

Question

Which of the following statements is/are TRUE? (Mark all CORRECT choices)

• A. The expected number of comparisons in a successful linear search is $n$
• B. The expected number of comparisons in a successful binary search is $O(\log n)$
• C. The best case runtime of linear search is asymptotically better than binary search
• D. In worst case binary search can lead to $\Omega(n)$ comparisons

Answer 1

Only B option is true here.

The expected number of comparisons in a successful linear search is $\lceil n/2 \rceil$ as the successful item is equally likely to be in any of the $n$ locations.

In best case both linear search and binary search can work in $O(1)$ time as the searched item should be the first element.

In worst case also binary search can work in $\Omega(\log n) $ comparisons as after each search half the elements get eliminated.

Comments

What is the other reason then?🤔

If it's not the "only"

---

Oh. If you used "only" to mean "single reason", then it's fine. I thought "only" was used to mean "less important".

---

Yes,

Thank you!