Introduction

If you are asking whether your algorithm is O(n) or whether O(n - 1) is more accurate, the Big O answer is O(n). Big O notation ignores additive constants, so n - 1, n + 100, and 3n - 7 all belong to the same asymptotic growth class.

Why O(n - 1) and O(n) mean the same thing

Big O describes how running time grows as n gets large. It does not try to preserve every constant or off-by-one detail. Mathematically, n - 1 is bounded above by n for all n >= 1, so if an algorithm takes n - 1 steps, it is certainly O(n).

That is why this loop is O(n):

1def sum_rest(values):
2    total = 0
3    for i in range(1, len(values)):
4        total += values[i]
5    return total

If len(values) = n, the loop runs n - 1 times. The exact count is n - 1, but the asymptotic class is still linear, so the correct Big O description is O(n).

Exact count versus asymptotic class

There are three different levels of description people often mix together:

1. Exact step count, such as T(n) = n - 1
2. Tight asymptotic growth, such as Theta(n)
3. Upper bound, such as O(n)

If you want the most precise expression for a simple loop, write the exact recurrence or exact count:

T(n) = n - 1

If you want the asymptotic growth class, write:

Theta(n)

If you only want a correct Big O upper bound, write:

O(n)

All three can be correct at the same time, depending on what level of detail you are aiming for.

Why O(n - 1) is unusual notation

People rarely write O(n - 1) because it keeps detail that Big O intentionally throws away. It is not wrong in a literal sense, but it is not idiomatic and it does not communicate anything useful beyond O(n).

For example:

• 'O(n - 1) simplifies to O(n)'
• 'O(2n + 5) simplifies to O(n)'
• 'O(1000n) simplifies to O(n)'

That is the whole point of the notation: to focus on growth rate, not exact constants.

A quick proof intuition

To show n - 1 is O(n), you only need a constant c and a threshold n0 such that:

n - 1 <= c * n

For all n >= 1, choosing c = 1 already works because n - 1 <= n. So n - 1 is O(n).

If you want to be even more precise, it is also Theta(n) because it grows linearly both above and below by constant multiples of n.

When exact counts actually matter

Exact counts matter when:

• you are comparing two linear-time implementations with different constants
• you are doing low-level performance tuning
• you are proving a recurrence carefully
• the assignment explicitly asks for an exact formula

In those cases, saying n - 1 can absolutely be more informative than saying O(n). The mistake is thinking that more exact arithmetic should always be written inside Big O notation itself.

A good pattern is:

The loop executes exactly n - 1 times, so T(n) = n - 1 and therefore the algorithm is Theta(n), hence also O(n).

That is both precise and idiomatic.

Common Pitfalls

The most common mistake is treating Big O as if it were an exact running-time formula. It is not. It is an asymptotic upper bound.

Another issue is writing overly specific expressions such as O(n - 1) or O(3n + 2) and assuming they are somehow more correct than O(n). They are not more informative in Big O terms.

People also mix up O, Theta, and exact counts. If you care about precision, use the right notation for the right purpose instead of overloading Big O.

Finally, do not ignore context. In interviews and algorithm classes, O(n) is usually the expected answer for an n - 1 loop. In a proof-heavy class, you may also be expected to provide the exact count or a Theta bound.

Summary

• If a function takes n - 1 steps, its Big O complexity is O(n).
• 'O(n - 1) is not useful in practice because Big O ignores additive constants.'
• The exact count can still be written as T(n) = n - 1.
• If you want a tight asymptotic description, use Theta(n).
• Use exact formulas for precision and Big O for growth class, not as interchangeable notations.