Counting Operations

Big-O Notation

Keeping Only the Essential

Counting precisely 3n^2 + 5n + 8 operations is too much detail. When n becomes large, only the strongest term really matters. Big-O notation (written O, the letter O as in "order of magnitude") formalizes this idea: we keep the dominant term and discard the rest.

Two simplification rules:

   3n^2 + 5n + 8       ->   O(n^2)    (we keep only the strongest term)
        7n             ->   O(n)      (we discard the constant 7)

We ignore multiplicative constants: 7n and n grow in the same way (doubling n doubles both). We write O(n) for both.
We keep only the dominant term: in n^2 + n, the n^2 overwhelms the n as soon as n is large. We write O(n^2).

Why These Simplifications Are Legitimate

The goal of Big-O is to describe large-scale behavior, not to predict an exact time. But at large scale, an algorithm in 100n remains infinitely preferable to an algorithm in n^2:

   n = 10 000 :
     100 n   = 1 000 000        (one million)
     n^2     = 100 000 000      (one hundred million)

Even with a constant of 100, O(n) wins by a wide margin. The constant becomes negligible compared to how the term grows. That's why we can afford to ignore it.

Reading a Loop

In practice, complexity can be read directly from the structure of the code:

# O(1)  : constant cost, independent of n
x = liste[0]

# O(n)  : a loop that goes through the n elements
for x in liste:
    traiter(x)

# O(n^2) : a loop INSIDE a loop
for x in liste:
    for y in liste:
        traiter(x, y)      # (executed n x n = n^2 times)

A loop nested inside another multiplies the costs: two loops over n give O(n^2), three give O(n^3). Two loops one after the other (not nested) add up: O(n) + O(n) = O(2n) = O(n).

What O Doesn't Tell You

Big-O describes a trend, not a value. It doesn't say that an O(n) is always faster than an O(n^2) for one specific small n (hidden constants can flip the ranking on small inputs). It says that beyond a certain size, and forever after, O(n) wins. It's a guarantee about scaling.

In Summary