What's the Time Complexity of Linear Search vs Binary Search?

Linear search has worst-case time complexity $O(n)$, while binary search has worst-case time complexity $O(\log n)$. Binary search is therefore more efficient for large data sets, but it requires the data to be sorted and efficiently indexable.

How Linear Search Works

Linear search examines elements sequentially until it finds the target or reaches the end of the data structure. For $n$ elements, the target may be found immediately, but in the worst case all $n$ elements must be checked.

For example, searching for the value 50 in [10, 20, 30, 40, 50] requires five comparisons. Doubling the number of elements can approximately double the maximum number of comparisons, producing linear growth.

How Binary Search Works

Binary search compares the target with the middle element of a sorted collection. It then eliminates half of the remaining search area after each comparison.

For $n = 1024$ elements, binary search requires at most about $\log_2 1024 + 1 = 11$ comparisons, depending on the counting convention. This repeated halving produces logarithmic growth.

A common misconception is that binary search is always the better algorithm. If data is unsorted, the cost of sorting it may outweigh the benefit of binary search for a single search. Linear search is also suitable for small collections or structures without efficient indexed access.

IB Exam Technique

For B2.4 Programming algorithms, state the relevant case, give the correct Big O notation, and justify it through comparisons: linear search checks items one by one, whereas binary search halves the search area. If asked to compare suitability, mention the sorted-data requirement rather than discussing complexity alone.