What Is Big O Notation?

Big O notation is a formal way of describing how the cost of an algorithm grows as its input grows, discarding constant factors and lower-order terms. Writing O(f(n)) says the work is bounded above by some constant multiple of f(n) once n is large enough. It is a promise about a family of inputs, not a measurement of one run, and it never claims the algorithm is exactly that fast.

The derivation rules are few. Sequential statements add their costs, so the total is dominated by the largest term. A loop running n times with a constant-cost body is O(n). A loop inside a loop multiplies, giving O(n times m), while two loops that run one after the other add, so O(n) followed by O(n) stays O(n).

def count_operations(n, nested):
    ops = 0
    for i in range(n):
        ops += 1
        if nested:
            for j in range(n):
                ops += 1
    return ops

for n in (10, 20, 40):
    print(n, count_operations(n, False), count_operations(n, True))

The printed counts show the shape. The flat version performs exactly n operations, so doubling n doubles the work. The nested version performs n plus n squared operations, and the numbers confirm that doubling n roughly quadruples the work. That steep curve is what the quadratic label describes.

Here is the part interviewers press on: Big O is only an upper bound, so saying an algorithm is O(n squared) does not rule out that it is also O(n). When you know more, say Theta for a tight bound where the cost really grows like that function, or Omega for a lower bound. Saying O(n) when you mean Theta(n) is a habit worth dropping. Also name your variables, because a function over a list of length n and a text of length m may depend on both, which is why a bound is often written in terms of several inputs.

It is linear, O(n), because the loop touches every element exactly once and does a fixed amount of work per element. The running total is updated in place, so nothing extra grows with the length of the list.

def total(values):
    running = 0
    for value in values:
        running += value
    return running

print(total([1, 2, 3, 4, 5]))

Running it prints 15, the sum of the five values. The cost model counts element visits rather than arithmetic detail: one addition and one assignment per element, so the function performs roughly n additions for n inputs. Space is O(1) on top of the input, because only the accumulator variable grows.

The trade-off to mention is that a single pass is the fastest you can do if you must read every element at least once, but the moment you need something extra, such as the running maximum or a sum grouped by value, one pass can usually answer several questions at the same cost. There is also a much faster implementation for this specific job: the built-in sum function runs in C, so it is measurably quicker in wall-clock terms even though both are O(n). Interviewers like that answer, because it shows you know the complexity and the constant factor are different things, and that a faster constant never changes the asymptotic story.

Push back because O(n) hides three separate things: the true growth rate, the constant factor, and the input distribution the algorithm behaves well on. An algorithm can be O(n) and still be the wrong choice, because a rival algorithm is also O(n) but does a tenth of the work, or because the O(n) version reorders a list that was already sorted and paid for it in full.

The questions worth asking are concrete. What is n, exactly: the number of elements, the number of distinct values, the number of edges, or the bit length of the input? Does the bound depend on more than one variable, and if so are those variables multiplied or added? Is it a worst case or an average, and if it is an average, over what distribution of inputs? Is the work per iteration constant, or does the body itself grow?

Push further on the constant factor and on where the time actually goes. A Python-level O(n) scan costs far more per element than a compiled library doing the same job, so on real data the practical gap can be an order of magnitude even though the notations match. In the other direction, an O(n) loop that allocates inside the loop can lose to an O(n log n) loop that allocates once, because allocation and garbage collection dominate the measurement.

Finally, ask what the bound means for the input sizes that matter. A quadratic algorithm is fine on a hundred items and hopeless on ten million. The strongest answer you can give is a bound, plus one sentence about the largest input you expect and the hardware you expect to run on.