The linear search is the most basic searching algorithm – as input, it takes a list and a target item to find. As the name implies, it moves through the list item by item until the target is found. After finding the item, the algorithm returns the index, or position in the list, that the item was found at, or a message indicating that it was not found. This algorithm is also known as the sequential search. Linear searches can be performed on any list, sorted or unsorted.
In the worst case of a linear search, the item to be found is the very last element. In a list of size n, this means that n operations must be carried out as every item must be checked. Therefore, the worst-case time complexity of a linear search is O(n). However, in the best case only one operation must be carried out – if the item is the first in the list, the time complexity is O(1). The average case leads to a time complexity of O(n).