Chapter 51: DSA Linear Search Time Complexity
DSA Linear Search Time Complexity – Let’s understand this topic very clearly and honestly, like I’m sitting next to you explaining it slowly on a piece of paper so you can really see and feel how the time grows.
1. What Linear Search actually does (quick reminder)
Linear Search (also called Sequential Search) is the simplest possible searching method:
- You start from the first element
- You compare it with the target
- If it matches → found
- If not → move to the next element
- Keep going until you either find the element or reach the end of the array
Example array of 8 elements:
|
0 1 2 3 4 5 6 7 |
Index: 0 1 2 3 4 5 6 7 Value: 45 12 78 23 56 89 34 67 |
We are searching for 23.
2. Three Cases – Best, Average, Worst
Almost every time complexity question asks for three cases. Linear Search is one of the easiest to understand because the cases are very intuitive.
| Case | When does it happen? | Number of comparisons | Time Complexity | Real feeling (n = 1 million) |
|---|---|---|---|---|
| Best Case | Target is at the first position | 1 comparison | O(1) | Instant |
| Average Case | Target is somewhere in the middle (random position) | n/2 comparisons | O(n) | Half a million comparisons |
| Worst Case | Target is at the last position OR not present | n comparisons | O(n) | Full million comparisons |
3. Detailed Explanation of Each Case
Best Case – O(1)
Array: [23, 45, 12, 78, …] Target = 23
- Compare arr[0] with 23 → match!
- Stop immediately
Only 1 comparison → Time complexity = O(1) → Extremely fast, constant time
Worst Case – O(n)
Array: [45, 12, 78, 34, 56, 89, 67, 23] Target = 23
- Compare arr[0] → no
- arr[1] → no
- arr[2] → no
- …
- arr[7] → yes
8 comparisons (for n=8)
Or if target = 99 (not present):
- Compare all 8 positions → 8 comparisons
General rule: In the worst case you always look at every single element → n comparisons
Time complexity = O(n)
Average Case – O(n)
Assume the target is equally likely to be at any position (or not present).
Possible positions: 1st, 2nd, …, nth, or not present.
Average number of comparisons:
(1 + 2 + 3 + … + n + n) / (n+1) = [n(n+1)/2 + n] / (n+1) ≈ n/2 + something small → still O(n)
Even if we consider only successful searches:
Average position ≈ n/2 → O(n)
Important: In almost all teaching and interview contexts, we say average case is also O(n).
4. Visual Table – How it grows
| n (array size) | Best Case comparisons | Average comparisons (≈) | Worst Case comparisons | Real time feeling (modern computer) |
|---|---|---|---|---|
| 10 | 1 | ~5 | 10 | instant |
| 100 | 1 | ~50 | 100 | instant |
| 1,000 | 1 | ~500 | 1,000 | instant |
| 10,000 | 1 | ~5,000 | 10,000 | instant |
| 100,000 | 1 | ~50,000 | 100,000 | instant |
| 1,000,000 | 1 | ~500,000 | 1,000,000 | ~0.001–0.01 seconds |
| 10,000,000 | 1 | ~5 million | 10 million | ~0.01–0.1 seconds |
Conclusion from the table:
Linear Search is actually very fast in practice for most real-world array sizes (even n = 10 million is usually < 0.1 seconds). But theoretically we still say O(n) because time grows linearly with n.
5. Summary – What you should say in interviews
“Linear Search has O(1) time complexity in the best case when the target is found at the first position. In the worst case (target at the end or not present) and in the average case (target at random position), it requires O(n) comparisons because in the worst case we must check every element once. Therefore, the overall time complexity is O(n). Space complexity is O(1) — it only uses a constant amount of extra space. It is very simple to implement and works well when the array is small or unsorted, but it becomes inefficient for very large arrays compared to Binary Search (O(log n)) on sorted data.”
6. Quick Cheat Sheet – Linear Search Time Complexity
| Question | Answer |
|---|---|
| Best-case time complexity | O(1) |
| Average-case time complexity | O(n) |
| Worst-case time complexity | O(n) |
| Space complexity | O(1) |
| Stable? | — (search, not sort) |
| When to use | Small arrays, unsorted data, one-time search, when simplicity is more important than speed |
Do you want to continue deeper into any part?
Common follow-up questions:
- Linear Search vs Binary Search – when to choose which
- How many comparisons exactly in average case (proof)
- Linear Search on linked list vs array
- When is O(n) acceptable in real interviews
- Can we make Linear Search faster? (spoiler: not really, unless data has special properties)
Just tell me which one you want next — I’ll explain it in the same calm, detailed, teacher style with clear examples 😊
