Concepts / Big O Notation

Big O Notation

Computational complexity measures the number of operations an algorithm performs.

  • Programming

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.

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

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.

assumesrepeated across the algorithmconnects work to timeAbstract machineunderlying modelOne operationc secondsOperation countalgorithmic workRunning timetime measure
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.

firstthen extend the viewexamineFixed learningproblem(Z, H, ℓ)Measure computationcount operationsSequence of taskstasks varyRate of changecomplexity across tasks
What happens when we first count an algorithm's operations and then express that count as a function of the input size?
  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. Examine a sequence of learning tasks and study the rate at which the measured complexity changes across that sequence.

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.

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

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

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

Reading O(f) Statements

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.

described withprovides growth formcontextrequired constantcondition applies to everyAlgorithmrunning time or operationcountLearning taskfixed problem or tasksequenceO(f)formal growth statementfgrowth functioncconstant operation timeDprobability distribution
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.

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.

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

Mistakes in Interpretation

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

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

    Fix: Begin by asking how much computational work the algorithm performs.

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

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

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

  • Describing learning-algorithm complexity using only one fixed task.

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

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

  • Treating O(f) as an isolated label.

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

    Fix: 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. Computational complexity measures the number of operations an algorithm performs.
  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. 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. 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. Big O reasoning focuses on the growth of computational work, not on whether code looks short or complicated.

Key Takeaways

  • 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

  • Computational Complexity
  • Learning Algorithms
  • Running Time Analysis