Learning pathOriginal reference
Lesson 6 of 12

Describe growth with Big-O

Name the input sizes and separate operation counts, growth bounds, and actual runtime.

First choose what n means

For an array, n can mean its active length. For a string, L is its stored character count. A matrix has independent row and column counts r and c. A divisor test measures the numeric value x, which is different from the number of digits used to write x.

The source uses a fixed-width unit-cost model: ordinary arithmetic, comparison, assignment, and valid array indexing have constant cost. This is a useful model for bounded C++ inputs, not a promise that arbitrary-precision arithmetic or a whole long string operation takes one step.

An upper bound is not a stopwatch

A count such as 3n + 7 grows linearly, so O(n) describes an asymptotic upper bound. O(1) means a bounded amount of work independent of the named size, not literally one instruction. For 2n² + 5n + 8, the quadratic term dominates as n grows.

Θ(n) describes a tight bound, with matching upper and lower growth. Big-O itself does not mean worst case. A linear search has constant best-case work when the first element matches, and linear worst-case work when the target is absent. Average-case claims need a stated input model.

Sequential costs add

One n-element scan followed by another makes 2n body visits, so its growth is still O(n). Scans of independent lengths n and m cost O(n + m). A fixed stride such as i += 3 changes the number of visits by a constant factor, not the linear growth.

For a conditional, count the condition plus the executed branch. A worst-case bound uses the most expensive reachable branch; mutually exclusive branches do not both run. A function called by the condition may itself be expensive.

C++23
// Complete C++23 program. Input: 0 <= n,m <= 1000000.
#include <iostream>
int main() {
    int n = 0, m = 0;
    std::cin >> n >> m;
    long long visits = 0;
    for (int i = 0; i < n; ++i) ++visits;
    for (int j = 0; j < m; ++j) ++visits;
    std::cout << visits << '\n'; // n + m body visits
}

Growth explorer

Idealized operation counts show growth. Actual runtime also depends on the implementation and machine.

O(1)1
O(log n)7
O(n)100
O(n log n)665
O(n²)10,000

Bar lengths use a logarithmic scale. Logarithms use base 2.

Guided simulation · Change the inputs to test your understanding.

Pause & predict

One loop visits n elements, then another visits 5n elements. What is the total growth?

Choose an answer
Try it yourself

Turn the idea into code

For 0 ≤ n ≤ 10⁶, count the body visits in for (int i = 0; i < n; i += 3). Give an exact count, a tight growth bound, and auxiliary space. Check n = 0, 1, and 8.

Give me a hint

List 0, 3, 6, … below n. A partial final group still contributes one visit.

Show the explained solution

The exact count is ceil(n/3), or (n + 2) / 3 under these bounds: 0, 1, and 3 for the requested cases. Including setup, time is Θ(n + 1); conventional positive-size shorthand is Θ(n). The counter and index use O(1) auxiliary space.

Your notes

Ready for the next idea?

Mark complete when you can explain it yourself.

From a problem to a programIdentify the input, output, and constraints, then translate a small plan into C++.Variables, types, and remembered valuesChoose a representation, initialize it, and understand what assignment really changes.Arithmetic without surprisesPredict division and remainder, widen before multiplication, and format decimal answers.Conditions and logical decisionsBuild exclusive categories, combine comparisons, and protect operations with short-circuit logic.Optional: other ways to chooseRecognize switch for exact choices and the conditional operator for choosing a value.For loops: make repetition preciseTrace initialization, condition, body, and update—and avoid an extra iteration.While, do-while, and stopping rulesChoose a loop from its stopping condition and read the exact input format.Break, continue, and early answersDistinguish leaving a loop from skipping one iteration, without losing required input.Five patterns worth understandingUse sums, counts, best-so-far candidates, products, and flags to process a stream.Nested loops: rows and columnsTranslate a shape into two loop roles and count the total work.Take a number apart, one digit at a timeUse remainder and division to process decimal digits, including zero.Multiple cases and a debugging mindsetCombine the patterns, isolate each case, and test the boundaries that can break your idea.Arrays: give every value a placeUnderstand indices, initialization, capacity, active length, and the first safe array loop.Scan, count, search, and compareDistinguish values from positions and preserve the exact tie rule a problem asks for.Change a sequence without losing itUpdate, copy, compare, reverse, and inspect neighbours using the correct bounds.Matrices: think in two coordinatesTraverse tables, total rows and columns, inspect diagonals, and protect grid neighbours.Characters become stringsSeparate characters from numbers, then safely inspect and edit managed text.Read the text the problem actually givesChoose words or full lines, preserve empty cases, and reset only the state that needs it.Scan text: count, filter, transformBuild a result from matching characters without losing leading zeros or skipping shifted text.Join, compare, and find textLearn content comparison, lexicographical order, substring counts, and the not-found sentinel.