Introduction

When someone asks whether an algorithm is linear, the real question is whether its running time grows proportionally to the input size. The tricky part is that visual structure alone can be misleading. A single loop is often linear, but not always. Nested loops are often not linear, but sometimes still are. The right answer comes from counting how many times the core work can happen as the input grows.

What Linear Time Means

An algorithm is linear if its time complexity is O(n), where n is the size of the input. Informally, doubling the input size should roughly double the amount of work, ignoring constant factors.

A simple example:

1def sum_items(items):
2    total = 0
3    for value in items:
4        total += value
5    return total

This is linear because each element is visited once and each visit does constant work.

A Single Loop Is Not the Definition

People often identify linear time by spotting one loop. That is a useful clue, but it is not a proof. The key question is how many total iterations occur as a function of n.

For example, this is still linear even though the index jumps by two:

1def every_other(items):
2    count = 0
3    for i in range(0, len(items), 2):
4        count += 1
5    return count

The loop runs about n / 2 times, which is still O(n) because constant factors are ignored in asymptotic complexity.

Nested Loops Are Not Always Quadratic

A nested loop often suggests O(n^2), but not always. If the total amount of movement across both loops is still bounded by a constant multiple of n, the algorithm can remain linear.

A common example is the two-pointer pattern:

1def count_pairs(items):
2    left = 0
3    right = 0
4
5    while right < len(items):
6        if items[right] % 2 == 0:
7            right += 1
8        else:
9            left += 1
10            right += 1
11
12    return right - left

Even though there are multiple moving parts, each pointer advances only forward. The total number of pointer moves is still proportional to n, so the runtime is linear.

Watch for Hidden Work Inside the Loop

A loop that looks linear can become non-linear if each iteration performs work that itself depends on n.

def bad_example(items):
    for i in range(len(items)):
        print(items[:i])

The outer loop runs n times, but items[:i] creates slices of increasing size. The total work accumulates to more than linear time. That is why complexity analysis should focus on the cost of the whole iteration body, not just the loop header.

Consider Input Representation Carefully

Complexity also depends on what operations cost for the underlying data structure. Accessing the ith element of an array-like list is constant time. Doing the same thing on a linked list is not.

So an algorithm may be linear for one structure and slower for another, even if the high-level pseudocode looks identical. Always ask what the primitive operations cost on the actual representation.

A Good Mental Test

To decide whether an algorithm is linear, ask:

1. What is the input size n.
2. What is the core unit of work.
3. How many times can that work happen in the worst case.
4. Are there hidden sub-operations that scale with n too.

If the total work can be bounded by a constant multiple of n, then the algorithm is linear.

Amortized Linear Time Still Counts

Some algorithms do occasional expensive work but remain linear overall because the expensive steps do not happen often. Dynamic array append is the classic example: some appends trigger a resize, but the average cost across many appends is still constant, so processing n appends is amortized linear.

This matters because the runtime story is sometimes about total accumulated work, not per-step worst-case cost in isolation.

Common Pitfalls

• Declaring an algorithm linear just because it has one visible loop.
• Declaring an algorithm non-linear just because it has nested loops without checking the total number of pointer or index moves.
• Ignoring expensive operations hidden inside what looks like a simple loop body.
• Forgetting that complexity depends on the underlying data structure and primitive operation costs.
• Mixing average-case, amortized, and worst-case reasoning without stating which one is being analyzed.

Summary

• A linear algorithm performs work proportional to input size, which is written as O(n).
• Loop shape alone is not enough to prove linearity.
• Nested control flow can still be linear if total movement or work stays proportional to n.
• Hidden costs inside each iteration often change the true complexity.
• The safest way to answer “is this algorithm linear” is to count the total worst-case work, not just inspect the syntax.