Complexity classes

Algorithmic reasoning = predicting what code does and what it costs, before running it. The exam's favorite costs:

• O(1) — constant: one comparison, one assignment. Array indexing a[5] is O(1) no matter how big a is.
• O(n) — linear: work grows in step with the input. One pass over n elements (sum, max, count) is O(n).
• O(n²) — quadratic: a loop inside a loop, each over n. All pairs, all grid cells, most "compare everything to everything" algorithms. 100 elements → 10,000 steps; 10,000 elements → 100,000,000 steps. Quadratic code is the one that times out.

for (int i = 0; i < n; i++) {        // n times
    for (int j = 0; j < n; j++) {    // n times each → n * n total
        // O(n^2)
    }
}

Logarithmic intuition: binary search halves the remaining range each step, so 1,000,000 elements need ~20 steps. You only need the intuition on this exam — halving beats scanning.