C++UCS301
Algorithm AnalysisC++17

Order Arithmetic

Rules for loops, branches, sequential blocks, and recurrences let us derive a program's overall asymptotic complexity.

What to understand

  • Add costs for sequential work
  • Multiply costs for nested work
  • Take the maximum branch
  • Recognise common recurrences

Remember this

  1. 1Two consecutive O(n) loops remain O(n)
  2. 2Two nested O(n) loops give O(n²)
  3. 3Halving a range produces O(log n)

Detailed notes

Sequential blocks add costs, nested blocks multiply costs, and mutually exclusive branches contribute the cost of the selected branch—usually bounded by the maximum branch for worst-case analysis.

A loop's syntax can be misleading. Incrementing by one is linear, multiplying the counter is logarithmic, and an inner loop whose limit depends on the outer index often produces an arithmetic series.

How it works

  1. 1Analyse each statement or block independently.
  2. 2Write a summation when iteration counts vary.
  3. 3Simplify the resulting expression by dominant growth.
  4. 4For recursion, form and solve or recognise the recurrence.

Where it is used

  • Deriving complexity directly from code
  • Understanding divide-and-conquer algorithms
  • Spotting hidden quadratic work in repeated library calls

Common mistakes

  • Multiplying consecutive loop costs instead of adding
  • Calling every nested loop O(n²)
  • Ignoring the cost of a function invoked inside a loop

C++ implementation

C++17 reference
main.cpp

Sequential versus nested work

Sequential costs add and nested costs multiply. O(n) + O(n²) simplifies to O(n²).

for (int value : values) {       // O(n)
    sum += value;
}

for (int i = 0; i < n; ++i) {    // O(n^2)
    for (int j = 0; j < n; ++j) {
        if (a[i] == b[j]) ++matches;
    }
}

// Total: O(n + n^2) = O(n^2)
11 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.