O(n)

What it means

O(n) means the amount of work grows along with the size of the input.

If the input doubles, the work usually doubles too.

Common shape

The classic case is a single pass:

for (const item of items) {
  process(item)
}

You look at each element once.

When it matters

O(n) is often a good sign in array, string, and list problems.

It is not always the best possible answer.

But it is usually much better than repeating scans for no reason.

Better question

Instead of only asking “is this O(n)?”, ask:

1. how many passes am I making?
2. am I repeating work for no reason?
3. would extra memory reduce the cost?