A Common-Sense Guide to Data Structures and Algorithms

Same Algorithm, Different Scenarios

As we learned in the previous chapters, linear search isn’t always O(N). It’s true that if the item we’re looking for is in the final cell of the array, it will take N steps to find it. But where the item we’re searching for is found in the first cell of the array, linear search will find the item in just one step. Technically, this would be described as O(1). If we were to describe the efficiency of linear search in its totality, we’d say that linear search is O(1) in a best-case scenario, and O(N) in a worst-case scenario.

While Big O effectively describes both the best- and worst-case scenarios of a given algorithm, Big O Notation generally refers to worst-case scenario unless specified otherwise. This ...