Look past the number of loops
Count rectangular, triangular, shared-counter, and growing-chunk loops correctly.
Multiply only when the full work repeats
An inner m-iteration loop reset for each of n outer iterations gives nm body visits. With positive dimensions, that is O(nm). A fixed inner bound of five gives only 5n visits, so the work is linear.
For pairs with i < j, inner lengths are n − 1, n − 2, …, 0. They sum to n(n − 1)/2. Checking each unordered pair only once saves a constant factor but still has quadratic growth. A counter does not need to store the pairs, so auxiliary space can remain O(1).
// Complete C++23 program. Input: 0 <= n <= 1000.
#include <iostream>
int main() {
int n = 0;
std::cin >> n;
long long visits = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) ++visits;
}
std::cout << visits << '\n';
}A counter can have one total budget
If j starts at zero before the outer loop and never resets, it can advance to n only once across the whole program section. Charging n advances to every outer iteration would count work that never occurs.
Move int j = 0 inside the outer loop and the analysis changes: each outer iteration starts a fresh full scan, producing n² increments. Trace where variables are initialized before attaching a complexity label.
// Analysis fragment inside a function. Contract: 0 <= n <= 1000000.
int j = 0;
for (int i = 0; i < n; ++i) {
while (j < n) ++j;
}
// j advances n times in total; outer overhead is also linear.Different inner lengths must be summed
If the outer widths are 1, 2, 4, … and the inner loop visits width elements, the total is a geometric sum. Up to the largest power 2ᵏ ≤ n, it is 2ᵏ⁺¹ − 1, which is less than 2n. The tight growth is linear even though there are nested loops.
For a rectangular loop with m = 0, there are no inner body visits, but n outer tests still occur. A precise bound covering that boundary is O(1 + n + nm). Keep this distinction when comparing exact visits with total running work.
Growth explorer
Idealized operation counts show growth. Actual runtime also depends on the implementation and machine.
O(1)1O(log n)7O(n)100O(n log n)665O(n²)10,000Bar lengths use a logarithmic scale. Logarithms use base 2.
Guided simulation · Change the inputs to test your understanding.
A triangular loop visits n(n − 1)/2 pairs. Is its time linear because it does roughly half of n² checks?
Turn the idea into code
An outer loop uses widths 1, 2, 4, … up to n. For each width, an inner loop makes exactly width visits. Find the visits for n = 10 and justify the general growth. Assume 1 ≤ n ≤ 10⁶ and a long long width.
Give me a hint
The widths below 10 are 1, 2, 4, and 8. Add them rather than multiplying the number of widths by 10.
Show the explained solution
The count is 1 + 2 + 4 + 8 = 15. For any n ≥ 1, the geometric sum is less than 2n and at least a constant fraction of n, so the total is Θ(n), with O(1) auxiliary space.
Your notes
Mark complete when you can explain it yourself.