Big O & growth

How does the work grow?

Complexity describes how resource use grows with input size. Big O gives an asymptotic upper bound; Θ describes a tight growth rate. These tools help compare scaling without pretending to predict exact milliseconds on a particular machine.

Look at what changes as n increases.

Doubling a linear input roughly doubles the dominant work; doubling a quadratic input roughly quadruples it. Constants still matter for real runtimes, especially small inputs. Growth notation separates the long-run relationship with n from those constant costs.

Two consecutive passes add their work.

Assume n is nonnegative and visit does constant work. The first loop makes n visits and the second makes n more. That is 2n visits, giving linear tight growth, Θ(n). Two loops written next to each other do not automatically multiply their counts.

for (int i = 0; i < n; ++i) visit(i);
for (int j = 0; j < n; ++j) visit(j);

Watch what doubling does.

These illustrative counts compare n units of work with n² units. They are operation counts, not timings. The gap expands as n increases because the two expressions grow at different rates.

Count the bounds, not the indentation.

An outer loop with n iterations and an inner loop with exactly three iterations performs 3n bodies. With constant work per body, its tight growth is linear. Nested loops become quadratic when their combined work grows like n², not merely because one appears inside another.

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < 3; ++j) visit(i);
}

A constant fraction disappears each step.

Repeatedly halving a positive integer reaches zero after a number of steps that grows logarithmically with its starting value. Doubling the initial value adds about one more halving step. With constant work at each step, this is Θ(log n) as n grows.

while (n > 0) {
    visit(n); // constant work
    n /= 2;
}