Linear search runs in linear time. Its efficiency can be expressed as a linear function, with the number of comparisons to find a target increasing linearly as the size of the list, N, increases.
The time complexity for linear search in Big-O notation is O(N).
A time complexity of O(N) means the number of comparisons is proportional to the number of elements, N, in the list. With a list with twice as many elements, linear search will take at most twice as long to perform the search. The time complexity of linear search is also dependent on the best case, worst case, and average case scenarios.
What is an example where linear search would be an good choice to search for values? What is an example where linear search would be a bad choice to search for values?