Linear Time On

Linear Time: O(n)

Imagine you are handed a stack of n exam papers and asked to find the highest score. There is no shortcut: you must look at every paper at least once, because any paper you skip could be the winner. If the stack doubles in size, your work roughly doubles too. That direct proportionality between the amount of input and the amount of work is exactly what we call linear time, written O(n).

The intuition is: touch each item a constant number of times. Whether you touch each item once, or twice, or five times, the total work still grows in a straight line as the input grows. That is why we drop constant factors and simply say O(n).

Precise definition

An algorithm runs in O(n) time if there exist constants c > 0 and n0 such that for all input sizes n ≥ n0, the number of basic operations T(n) satisfies T(n) ≤ c · n. In words: beyond some starting size, the runtime never exceeds a fixed constant times n.

Big-O is an upper bound. Constant factors and lower-order terms disappear: 3n + 7, n/2, and 100n + 5000 are all O(n), because for large n the leading n term dominates and the constants fold into c. The defining trait of linear time is that work scales in lock-step with input size — no exponents, no logarithms multiplying the n.

A worked example — counting the operations

Let's find the maximum of an array of n = 5 numbers: [4, 9, 2, 9, 6]. The algorithm keeps a running best and compares every element to it.

• Initialise best = 4 (first element). 0 comparisons so far.
• Compare 9 > 4? Yes → best = 9. (1)
• Compare 2 > 9? No. (2)
• Compare 9 > 9? No. (3)
• Compare 6 > 9? No. (4)

For n elements we do exactly n − 1 comparisons. For n = 5 that is 4; for n = 1000 it is 999. The count T(n) = n − 1 is bounded by c · n with c = 1, so this is O(n). Notice the answer is identical whether the max sits first or last — we still scan all n. That is why best, worst, and average cases here are all Θ(n) for n ≥ 1: the loop cannot terminate early without risking a missed maximum. Edge cases: n = 0 (empty) — no max; algorithm must define an error/optional return (0 comparisons). n = 1 — initialise best to the only element, 0 comparisons, still O(1) work and consistent with T(n)=n−1.

Common pitfalls & what an interviewer probes

• Nested loops are not automatically O(n²). If the inner loop runs a fixed number of times (say 3), the total is still O(n). What matters is whether the inner work depends on n.
• Hidden linear costs. A loop that looks O(n) can become O(n²) if each iteration does an O(n) operation like list.contains(), string concatenation, or an arr.insert(0, x) that shifts everything. Interviewers love to plant these.
• Two separate passes are still O(n). Scanning an array once to sum and again to find the max is 2n operations = O(n), not O(n²). Sequential loops add; nested loops multiply.
• Input size vs value. Looping k times where k is a number in the input is O(k), which can be exponential in the number of bits — a classic trap in "pseudo-polynomial" questions.
• A common probe: "Can you do better than O(n)?" Often the honest answer is no — if you must read all the data, O(n) is a lower bound. Recognising that a problem requires examining every element is itself the insight.

When it matters + trade-offs vs neighbours

O(n) is the sweet spot for problems where you genuinely must inspect all the data: summing, filtering, a single pass to build a frequency map, or two-pointer / sliding-window techniques. It is usually the best achievable bound whenever the answer depends on every input element.

• Versus O(1): constant time (e.g. a hash-map lookup, array index) does not grow with input — always preferable, but only possible when you can jump straight to the answer without scanning.
• Versus O(log n): sub-linear, achievable only on structured data (a sorted array binary-searched, a balanced tree). It beats O(n) but requires you not to touch every element.
• Versus O(n log n): the cost of comparison sorting and many divide-and-conquer algorithms. A frequent trade-off: an O(n) hash-based solution using extra memory versus an O(n log n) sort using O(1) extra space. Interviewers reward naming this space-time trade-off explicitly.

Rule of thumb at scale: for n = 107, an O(n) pass finishes in milliseconds, while O(n²) would need ~10¹⁴ operations — hours. That gap is why spotting a linear solution is so valuable.

Key takeaways

• O(n) means work grows in direct proportion to input size — double the data, double the work; constants and lower-order terms drop out.
• Formally, T(n) ≤ c · n for large n; a single pass touching each element a constant number of times is the canonical shape.
• Sequential loops add (still O(n)); nested loops whose inner work depends on n multiply (O(n²)) — and watch for hidden linear operations inside a loop.
• When the answer depends on every element, O(n) is typically optimal; beating it (O(log n), O(1)) demands structure or a lookup shortcut, and O(n) vs O(n log n) is often a space-time trade-off worth naming aloud.