Linear time describes an algorithm whose execution time grows in direct proportion to the size of its input. If you double the amount of data, the work takes roughly twice as long. In computer science notation, linear time is written as O(n), where “n” represents the number of items the algorithm processes.
How O(n) Works
The “O” in O(n) stands for “order of,” and it’s part of a system called Big O notation that computer scientists use to describe how an algorithm’s performance scales. When an algorithm runs in O(n), there’s a fixed constant such that, for all sufficiently large inputs of size n, the algorithm takes at most that constant times n steps to finish. The key insight is that the constant doesn’t matter much. Whether it takes 2n steps or 50n steps, the growth pattern is the same: a straight line when you plot execution time against input size.
Mathematically, a linear function looks like f(n) = d × n + k, where d and k are constants. Big O notation strips away those constants and focuses on the dominant term, so any function that grows proportionally to n is classified as O(n). Even something like n + log n qualifies as O(n), because for all values of n greater than 1, the expression stays between n and 2n.
What Linear Time Looks Like in Practice
The simplest example is walking through every item in a list, one by one. If you have an array of 1,000 numbers and you want to find the smallest one, you have to look at each number exactly once. There’s no shortcut. That single pass through the data is what makes the operation O(n).
Other common linear time operations include:
- Finding the maximum value in an unsorted list
- Calculating an average by summing all elements
- Searching for a specific item in an unsorted collection
- Counting occurrences of a particular value
The common thread is that these tasks need to inspect each data point individually. There’s no way to skip elements and still guarantee a correct answer, so the algorithm must touch every one.
How Linear Time Compares to Other Speeds
O(n) sits in the middle of the performance spectrum. It’s considered “fair” in terms of efficiency, faster than many alternatives but slower than the best-case scenarios.
An O(1) algorithm (constant time) takes the same amount of time regardless of input size. Looking up a value by its index in an array is O(1) because you jump directly to the right spot. O(log n) algorithms, like binary search, are also faster than linear because they cut the remaining work in half at each step. For a million items, a binary search might need only about 20 comparisons instead of a million.
On the slower side, O(n log n) is the speed of efficient sorting algorithms. O(n²), quadratic time, means the work grows with the square of the input. Processing 1,000 items takes about a million steps, and 10,000 items takes about 100 million. A linear algorithm is always asymptotically better than a quadratic one, meaning that no matter how large the constant factors are, the linear algorithm will eventually win as the input grows large enough.
Beyond quadratic, things get dramatically worse. O(2ⁿ) and O(n!) grow so fast they become impractical for even moderately sized inputs.
Why Linear Time Matters
When you’re writing code or evaluating someone else’s, recognizing whether an operation runs in linear time helps you predict how it will behave at scale. A function that handles 100 records in a fraction of a second will handle 100 million records in a proportionally longer, but still manageable, timeframe. That predictability is what makes O(n) a comfortable baseline for many real-world applications.
The practical question is often whether you can do better. If your algorithm scans every element in a list to find one item, that’s O(n). But if you reorganize the data into a structure that supports faster lookups (like a hash table, which offers near-constant time access), you can avoid the linear scan entirely. Understanding that your current approach is O(n) is the first step toward knowing when and why to optimize.
For many problems, though, linear time is the best you can achieve. If your task inherently requires looking at every piece of data, such as summing all values or printing every element, no algorithm can do it faster than O(n). That’s the floor, and hitting it means your solution is already optimal.