Introduction

When someone asks whether an algorithm runs in O(n), the real task is to count how the work grows as input size grows. Linear time means the amount of work increases proportionally with the number of input elements, up to constant factors. To answer correctly, you need to identify the dominant operations, not just count the number of loops.

What O(n) actually means

An algorithm is O(n) if its running time grows at most linearly with input size n. That does not mean every line runs exactly once. It means the total amount of work is bounded by some constant multiple of n for large enough inputs.

For example, this is linear:

1def contains_negative(values):
2    for value in values:
3        if value < 0:
4            return True
5    return False

In the worst case, the loop inspects every element once, so the runtime is O(n).

Even this is still O(n):

1def sum_and_count(values):
2    total = 0
3    count = 0
4
5    for value in values:
6        total += value
7
8    for _ in values:
9        count += 1
10
11    return total, count

There are two loops, but each loop is linear, so the total is O(n + n), which simplifies to O(n).

When an algorithm is not O(n)

The most common reason an algorithm is not linear is nested iteration over the same input.

1def all_pairs(values):
2    pairs = []
3    for i in range(len(values)):
4        for j in range(len(values)):
5            pairs.append((values[i], values[j]))
6    return pairs

This does n * n pairings, so the runtime is O(n^2), not O(n).

Another common trap is hidden work inside operations that look cheap. For example, membership checks on a Python list are linear:

1def has_duplicates(values):
2    seen = []
3    for value in values:
4        if value in seen:
5            return True
6        seen.append(value)
7    return False

The outer loop is linear, but value in seen is also linear in the size of seen, so the full algorithm becomes O(n^2) in the worst case.

If you switch to a set:

1def has_duplicates_fast(values):
2    seen = set()
3    for value in values:
4        if value in seen:
5            return True
6        seen.add(value)
7    return False

Now the membership check is typically constant time on average, and the algorithm becomes O(n).

How to analyze an algorithm properly

A reliable workflow is:

1. Define what n represents.
2. Count how many times the dominant operation runs.
3. Replace low-level implementation details with their complexity.
4. Drop constants and lower-order terms.

For example, suppose n is the number of elements in a list. If each element is touched once and each touch does constant-time work, the algorithm is linear.

But if each element triggers a full scan of the same list, the algorithm is quadratic. That is why "there is only one loop" is not enough to prove O(n).

Best case versus worst case

When people ask whether an algorithm "runs in O(n)," they usually mean worst-case time complexity unless stated otherwise.

Consider:

1def find_zero(values):
2    for value in values:
3        if value == 0:
4            return True
5    return False

Best case: the first value is zero, so the runtime is constant.

Worst case: no value is zero, so every element is checked. That makes the worst-case time O(n).

Common Pitfalls

The biggest mistake is counting loops instead of operations. Two back-to-back loops can still be O(n), while one loop containing a linear-time operation can become O(n^2).

Another issue is ignoring the cost of library calls. Searching a list, concatenating strings repeatedly, or copying slices can change the true complexity.

Developers also forget to define n. In some problems, n might be the number of nodes, edges, characters, or matrix cells, and the complexity statement depends on that definition.

Finally, do not confuse upper bounds with exact runtime. Saying an algorithm is O(n) does not mean it is always proportional to n; it means it does not grow faster than linear asymptotically.

Summary

• 'O(n) means the runtime grows at most linearly with input size.'
• Multiple linear passes are still O(n).
• Nested linear work often turns an algorithm into O(n^2).
• Hidden costs inside loop bodies matter as much as the loops themselves.
• Analyze dominant operations, not just the visual structure of the code.