O(n): Linear Time
You'll learn what linear time complexity means and how to recognize algorithms that process each element exactly once.
The Core Idea
An algorithm runs in O(n) time when its number of operations grows directly proportional to the input size. If you double the input, you roughly double the running time. If you have 10 elements, you do ~10 operations. With 100 elements, ~100 operations.
Think of it like reading a book page-by-page: to read a 200-page book takes twice as long as reading a 100-page book. You process each page once, linearly.
Common Linear Time Patterns
Single-pass array traversals are the classic example:
for i from 0 to n-1:
process array[i]
This loop visits each element exactly once, performing constant-time work per element. Total operations: n × O(1) = O(n).
Examples from your previous lessons:
- Linear search: checking each element until you find your target (or reach the end)
- Finding max/min: scanning through all elements once to track the largest or smallest
- Array reversal: visiting each element once to swap positions
- String traversal: processing each character in a string one time
Why It Matters
Linear time is often the best you can do when you must examine every element. You can't find the maximum value without looking at all the numbers, right? O(n) represents this necessary work.
Linear time scales predictably and reasonably well—much better than quadratic O(n²) from nested loops you've analyzed before.
Key Takeaway: O(n) linear time means your algorithm processes each input element once, making the runtime directly proportional to input size—a common and efficient pattern for single-pass operations.