When studying algorithms, one of the fundamental concepts you’ll encounter is time complexity—a measure of how the runtime of an algorithm grows relative to its input size. Among the simplest and most widely taught algorithms is linear search, also known as sequential search. While it’s easy to understand and implement, its efficiency can vary depending on the context in which it’s used. In this article, we’ll explore what linear search is, how it works, and—most importantly—the time complexity of linear search in different scenarios.
What Is Linear Search?
Linear search is an algorithm used to find a particular element in a list or array by checking each element one by one from the beginning to the end. If the element is found, the index is returned; otherwise, the search continues until the end of the list is reached.
Example:
Imagine searching for the number 7 in the list [3, 5, 7, 9, 11]. Linear search will:
- Check 3 → not a match
- Check 5 → not a match
- Check 7 → match found at index 2
It’s that simple—no sorting or pre-processing is required.
Time Complexity of Linear Search
The time complexity of an algorithm refers to how the runtime grows as the input size (n) increases. For linear search, this varies based on where the target element is located or if it exists in the list at all.
1. Best Case Time Complexity: O(1)
- When it occurs: The element is found at the very beginning of the list (index 0).
- Explanation: The algorithm only needs one comparison to find the target.
- Real-world example: Searching for the first contact in your phonebook by name.
2. Average Case Time Complexity: O(n)
- When it occurs: The element is equally likely to be anywhere in the list.
- Explanation: On average, half of the list will be scanned before finding the element.
- Formula: (n + 1) / 2 comparisons on average, which simplifies to O(n) in Big-O notation.
3. Worst Case Time Complexity: O(n)
- When it occurs:
- The element is at the very end of the list
- Or the element is not in the list at all
- Explanation: The algorithm must check all
nelements.
Why Linear Search Has Linear Time Complexity
Linear search doesn’t use any shortcuts or divide-and-conquer strategies. It checks every element one by one, so:
- If you double the size of your data, the time taken roughly doubles.
- Therefore, the time grows linearly with the input size.
This property gives the algorithm its name: linear search.
Space Complexity of Linear Search
While we focus on time complexity, it’s also worth noting the space complexity:
- Space Complexity: O(1)
- Why: Linear search only uses a constant amount of extra memory (like an index variable or a temporary placeholder), regardless of the size of the input array.
Comparison with Other Search Algorithms
| Algorithm | Time Complexity (Best / Average / Worst) | Requirements |
|---|---|---|
| Linear Search | O(1) / O(n) / O(n) | No sorting needed |
| Binary Search | O(1) / O(log n) / O(log n) | Requires sorted array |
| Hashing (Lookup) | O(1) / O(1) / O(n) | Requires hash table setup |
Note: Binary search is significantly faster than linear search on large, sorted datasets, but it can’t be used on unsorted data.
When to Use Linear Search
Despite its higher time complexity compared to other algorithms, linear search is still useful in many scenarios:
- Small datasets: For small lists, the performance difference is negligible.
- Unsorted data: When you don’t want to sort the data just for a one-time search.
- Simplicity: Great for quick prototypes or when algorithmic complexity isn’t a concern.
Practical Example: Linear Search in Python
pythonCopyEditdef linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i # Element found
return -1 # Element not found
# Example usage
my_list = [10, 23, 45, 70, 11]
print(linear_search(my_list, 70)) # Output: 3
Also read our ruby vs python article.
Real-World Applications of Linear Search
While linear search isn’t always the most efficient method, it’s still widely used in practical scenarios, such as:
- Searching in small or dynamically changing datasets
- Filtering or scanning logs
- Checking for duplicates in real-time systems
- Educational purposes to teach algorithmic basics
Final Thoughts
The time complexity of linear search is straightforward:
- Best case: O(1)
- Average case: O(n)
- Worst case: O(n)
Although not the most efficient algorithm for large datasets, linear search remains relevant due to its simplicity and zero prerequisites like sorting, according to MIT. Understanding its time complexity helps in choosing the right algorithm for the task at hand.
Whether you’re optimizing performance or just starting to learn about algorithms, knowing when to use linear search—and when not to—is a foundational skill in computer science.