Concepts / Big O Notation

Big O Notation

The central object being measured is the algorithm's operation count. Input size matters because complexity examines how that count changes as the relevant problem grows.

  • Programming
Interactive lab

Try it: Counting Operations: How Work Grows

Computational complexity as a count of operations: run a function once and count every basic operation (each costing a constant c on an abstract machine), then run it for a whole sequence of input sizes and compare how the count changes with growth functions 1, , and , which is what an O(f) statement describes.

How it works

  1. Stage 1, one fixed task: run the function at one size and count every operation on the lines marked "counted" (a comparison, a division, one feature of a distance).
  2. The abstract machine charges the same constant c microseconds per operation, so running time = c x count, whatever the code looks like.
  3. Stage 2, a sequence of tasks: run the same function again for every size 1..N and plot the count against the size.
  4. Doubling test: for in turn, compare at and at ; the first f for which that ratio stops growing is the growth class O(f).
  5. The ratio settles to a constant (1/2 for the pairs loop, d + 1 for nearest-neighbour search): the constant, lower-order terms and c rescale the curve but do not change its growth.

Default run (54 steps): Stage 1, one fixed task: run equal_pairs at n = 6 and count every operation on a line marked "counted". … count(n) <= 0.4844 x n^2 for every n from 2 to 32, and the ratio settles near 0.4844. That constant, the lower-order terms and c only rescale the curve, so the growth class is O(n^2).

Simplified: Five small, fixed functions with their counted lines chosen in advance (one comparison, division or feature step = one operation); their counts do not depend on the values, so the statement holds for every input of a size (the learning-theory definition also quantifies over every distribution D). The growth class is read from a finite sweep (N up to 64) with a doubling test and a 10 % tolerance; a real O(f) claim is about all sufficiently large sizes and needs a proof.

Educational simulation

Loading the simulation…

From Work to Complexity

When we ask how complex an algorithm is, we are not initially asking whether its code looks short or complicated. We are asking how much computational work it performs. Computational complexity measures that work by counting the operations required by the algorithm.

Small inputfewer operationsLarger inputmore operationsStill larger inputoperation count continuesto changeinput size increasesinput size increases
How does the number of operations performed by an algorithm change as the input size increases?
Key point

The central object being measured is the algorithm's operation count. Input size matters because complexity examines how that count changes as the relevant problem grows.

The Abstract Machine Assumption

An operation count is not automatically a measurement in seconds. To connect the count with time, the definition uses an underlying abstract machine and assumes that there is a constant c seconds per operation. Under this assumption, any operation can be performed in c seconds.

This assumption lets the definition measure computational work without depending on the details of one particular implementation. Instead of asking how long a specific implementation happens to take on a particular machine, we count the operations under the abstract-machine assumption.

Abstract machineunderlying modelOne operationc secondsOperation countalgorithmic workRunning timetime measureassumesrepeated across the algorithmconnects work to time
Why can different kinds of operations be treated as taking one constant unit of time on an underlying abstract machine?

Two Stages of Learning Complexity

A learning algorithm is not assigned its full complexity description in one move. The formal definition separates the task into two related views: first, complexity for one fixed learning problem; second, the way that complexity changes across a sequence of learning tasks.

Fixed learningproblem(Z, H, ℓ)Measure computationcount operationsSequence of taskstasks varyRate of changecomplexity across tasksfirstthen extend the viewexamine
What happens when we first count an algorithm's operations and then express that count as a function of the input size?
  1. 1
    Hold one learning problem fixed. The source represents it with the triplet (Z, H, ℓ): a domain set, a benchmark hypothesis class, and a loss function.
  2. 2
    Examine a sequence of learning tasks and study the rate at which the measured complexity changes across that sequence.
Worked example

Separating the Two Views

Imagine that a learning algorithm is evaluated first on one fixed learning problem and then across a sequence of related learning tasks.

  1. 1
    Stage one

    Keep the learning problem fixed, represented by (Z, H, ℓ), and ask how much computation the algorithm requires for that particular problem.

  2. 2
    Stage two

    Move from the individual problem to a sequence of learning tasks and examine how the measured complexity changes along that sequence.

Result

The complete description has both an individual-task view and an across-tasks view.

Reading O(f) Statements

Definition

In the source's formal treatment, O(f) is attached to a learning task, an algorithm, and a function f. The constant c must work for every probability distribution D mentioned in the definition. Thus, O(f) is part of a quantified statement about the algorithm's running time or computational work, not an isolated label attached to the algorithm.

Algorithmrunning time or operationcountLearning taskfixed problem or tasksequenceO(f)formal growth statementfgrowth functioncconstant operation timeDprobability distributiondescribed withprovides growth formcontextrequired constantcondition applies to every
How does a statement such as T(n) = O(f(n)) describe the relationship between an algorithm's actual operation count and its growth function?

The function f supplies the growth form used in the statement. The learning task identifies what problem is being analyzed, the algorithm identifies the computation being measured, and c connects the operation count to the abstract machine's time assumption. The requirement involving every probability distribution D makes the statement broader than a claim about one selected distribution.

Part of the statementRole
O(f)Expresses the growth form used for the computational-work statement.
fThe function whose growth is used in the formal description.
Learning taskIdentifies the learning problem or task sequence under consideration.
AlgorithmThe source of the operation count being measured.
cThe constant seconds-per-operation assumption.
DA probability distribution covered by the formal statement.

The formal statement combines a growth function with the task, algorithm, constant, and distributions involved.

Ignoring Surface Detail

Big O reasoning focuses attention on how operation counts change with the relevant input or task size. The source's definition emphasizes this rate of change rather than the appearance of the code. The useful comparison is therefore between the operation count and a growth function, within the formal assumptions about the machine, task, algorithm, constant c, and distributions D.

Implementationdetailsparticular implementationOperation countcomputational workGrowth functionfComplexity statementO(f)not the initial focusexamined throughexpressed as
What changes when the analysis focuses on how operation counts grow rather than on implementation details?

Mistakes in Interpretation

  • Common mistake

    Treating computational complexity as a judgment about code length or visual difficulty.

    What it looks like

    Calling an algorithm complex because its code looks long, without counting the operations it performs.

    Why it fails

    The source defines computational complexity through the number of operations performed by the algorithm.

    Do this instead

    Begin by asking how much computational work the algorithm performs.

  • Common mistake

    Ignoring the abstract-machine assumption when connecting operations to time.

    What it looks like

    Interpreting an operation count as a number of seconds without considering the constant c.

    Why it fails

    The definition uses an underlying abstract machine and assumes a constant c seconds per operation.

    Do this instead

    Keep the constant operation-time assumption in view when relating operation count to running time.

  • Common mistake

    Describing learning-algorithm complexity using only one fixed task.

    What it looks like

    Measuring one learning problem and stopping there.

    Why it fails

    The formal definition has a fixed-task stage and an across-tasks stage.

    Do this instead

    First measure one fixed learning problem, then examine the rate of change across a sequence of tasks.

  • Common mistake

    Treating O(f) as an isolated label.

    What it looks like

    Writing O(f) beside an algorithm without identifying the learning task, function, constant, or distributions involved in the formal statement.

    Why it fails

    The source presents O(f) as part of a quantified statement involving those elements.

    Do this instead

    Read O(f) together with the task, algorithm, function f, constant c, and every probability distribution D covered by the statement.

Check Your Understanding

MEDIUM

Explain the two stages used to define the complexity of a learning algorithm. In your answer, identify what is held fixed in the first stage and what changes in the second stage.

Hints
  • Use the triplet (Z, H, ℓ) when describing the fixed learning problem.
  • The second stage concerns a sequence of learning tasks and the rate at which complexity changes.
MEDIUM

A formal statement contains O(f), a learning task, an algorithm, a constant c, and every probability distribution D. Describe the role of each component without treating O(f) as a standalone label.

Hints
  • Start with O(f) and f as the growth description.
  • Then connect c to the abstract-machine assumption and D to the distributions covered by the statement.

Key Takeaways

  1. 1
    Computational complexity measures the number of operations an algorithm performs.
  2. 2
    An underlying abstract machine and a constant c seconds per operation connect operation counts with running time without depending on a particular implementation.
  3. 3
    Learning-algorithm complexity is defined in two stages: measure one fixed learning problem, then examine how that complexity changes across a sequence of tasks.
  4. 4
    O(f) is part of a formal statement involving a growth function, learning task, algorithm, constant c, and every probability distribution D covered by the definition.
  5. 5
    Big O reasoning focuses on the growth of computational work, not on whether code looks short or complicated.

At a glance

  • Complexity is a measure of an algorithm's operation count.
  • The abstract-machine model uses a constant operation time so that operation counting can represent computational work.
  • Learning complexity has a fixed-task stage and an across-tasks stage.
  • O(f) describes a formal growth relationship within a statement about a task, algorithm, constant, and distributions.

Related Topics

Related concepts

More concepts starting with B