Big-O and complexity: worked exercises

First-semester lectures started in mid-September (at the Politecnico di Milano on 14 September 2026), and in Fundamentals of Computer Science or in Algorithms and Data Structures one of the first “real” topics — after the programming revision — is computational complexity and Big-O notation. Where the calendar provides for a mid-term test (prova in itinere), it typically falls at the end of October or beginning of November (at the Politecnico from 29 October to 2 November 2026, so about five weeks from here); the winter exam session, at universities with an early calendar like the Politecnico, starts on 7 January 2027.

It is a topic that looks like “just theory” and is instead examined mostly through exercises: analysing a fragment of code and saying what its complexity is, proving a relationship with the formal definition, solving a recurrence. Here you will find the method for doing it without guessing.

What “complexity” really means

The complexity of an algorithm is a function that describes how the cost grows (time or memory) as the size of the input grows, which we call $n$ . It is not the time in seconds — that depends on the processor, the language, who else is using the machine — it is a way of describing growth that leaves all that aside.

It makes sense to distinguish three cases:

Worst case: the input that makes the algorithm do the maximum possible work. It is the one on which exam analysis is almost always based, because it gives a guarantee that is always valid.
Best case: the most favourable input.
Average case: the average cost over all possible inputs, weighted by probability. Harder to calculate, less often asked in the first exams.

The formal definitions: O, Ω, Θ

Big-O notation gives an upper bound on the growth of a function. We say that $f (n) = O (g (n))$ if there exist a constant $c > 0$ and a value $n_{0}$ such that:

f (n) \leq c \cdot g (n) for every n \geq n_{0}

In words: from a certain point on ( $n \geq n_{0}$ ), $f (n)$ never exceeds $g (n)$ up to a multiplicative constant. The constant $c$ and the threshold $n_{0}$ are exactly the two ingredients that a “prove $f (n) = O (g (n))$ ” exercise asks you to exhibit explicitly — it is not enough to say “it’s true”, you have to construct the pair $(c, n_{0})$ that makes it true.

The other two notations complete the picture:

f (n) = Ω (g (n)) ⟺ \exists c > 0, n_{0} : f (n) \geq c \cdot g (n) for every n \geq n_{0}

f (n) = Θ (g (n)) ⟺ f (n) = O (g (n)) and f (n) = Ω (g (n))

$Ω$ is the lower bound (the opposite of $O$ ), $Θ$ is the case where $f (n)$ is bounded both above and below by the same $g (n)$ : the growth is “exactly that”, not just “at most that”. A frequent conceptual mistake is using $O$ and $Θ$ as synonyms: saying that an algorithm is $Θ (n^{2})$ is a stronger statement than saying it is $O (n^{2})$ , because it also rules out that it could grow more slowly.

Practical rules for calculating complexity

In most exercises you don’t need to apply the formal definition every time: a few mechanical rules are enough.

Keep only the dominant term, and throw away the constants. $3 n^{2} + 5 n + 20$ is $O (n^{2})$ : for large $n$ the term $n^{2}$ dominates everything else, and the multiplicative constants ( $3$ , $5$ , $20$ ) don’t change the order of growth.
Instructions in sequence add up, but the worst term wins. An $O (n)$ loop followed by an $O (n^{2})$ loop costs $O (n + n^{2}) = O (n^{2})$ .
Independent nested loops multiply. Two nested for loops, each from $0$ to $n$ , give $O (n) \cdot O (n) = O (n^{2})$ .
Dependent nested loops have to be summed, not multiplied “by eye”. If the inner loop depends on the index of the outer one (for example the inner loop runs from $0$ to $i$ ), the total number of iterations is a sum, not a simple product — see the next section.
An index that doubles (or halves) at each iteration gives logarithmic growth. A loop for (int i = 1; i < n; i = i * 2) runs about $lo g_{2} n$ times, because it takes $lo g_{2} n$ doublings to go from $1$ to $n$ .

The case of dependent nested loops: Gauss’s sum

This exercise appears very often and is got wrong almost always in the same way:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        // O(1) operation
    }
}

The common mistake is to conclude “two nested loops, so $O (n^{2})$ ” without checking that the count really works out. In this case the total number of iterations of the inner loop, over all iterations of the outer one, is:

i = 0 \sum n - 1 i = 0 + 1 + 2 + \dots + (n - 1) = \frac{n ( n - 1 )}{2}

which is still $O (n^{2})$ — the final conclusion is right — but for the wrong reason if you get there “by eye” instead of by summing. It is worth being able to write this step out explicitly, because with differently dependent loops (for example an inner loop running from $0$ to $i$ ) the shortcut “nested so I multiply” gives precisely the wrong result, whereas the explicit sum does not.

The hierarchy of complexities

Ordering the most common growth functions, from slowest to fastest, is something worth having automatic:

1 < lo g n < n < n lo g n < n^{2} < n^{3} < 2^{n} < n!

To get a concrete idea of what this means in practice, here is a table with $n = 20$ and $n = 50$ (rounded values):

Complexity	$n = 20$	$n = 50$
$lo g n$	~4.3	~5.6
$n$	20	50
$n lo g n$	~86	~282
$n^{2}$	400	2,500
$2^{n}$	~1 million	~10^15
$n!$	~2.4×10^18	astronomical

The jump between $n^{2}$ and $2^{n}$ is what, in practice, decides whether an algorithm is usable on large inputs or not: an $O (2^{n})$ algorithm becomes impractical far sooner than intuition suggests, because every single extra element of the input doubles the work, rather than increasing it by a fixed amount.

Linear search, binary search, and sorting algorithms

Two search algorithms that come back in every exam:

Linear search: scans the array element by element until it finds the target (or the array ends). Worst case $O (n)$ : no assumption about the order of the data.
Binary search: requires a sorted array, and at each step halves the search space by comparing the target with the middle element. Worst case $O (lo g n)$ .

And three classic sorting algorithms, with the worst-case complexity that every exam wants you to know by heart:

Bubble sort: compares and swaps adjacent elements, $O (n^{2})$ .
Insertion sort: inserts each element in the correct position relative to the already sorted part, $O (n^{2})$ in the worst case (but almost $O (n)$ if the array is already nearly sorted — a detail that professors love to ask about).
Merge sort: recursively splits the array in half, sorts the halves, then merges them. $O (n lo g n)$ , always — even in the worst case, and that is precisely why it is preferred to the first two on large inputs.

Recurrences: the tree method

Many recursive algorithms have a cost described by a recurrence equation. The two that appear most often:

Binary search: $T (n) = T (n /2) + c$ — a single subproblem of half the size, plus a constant cost $c$ for the comparison.

Merge sort: $T (n) = 2 T (n /2) + c n$ — two subproblems of half the size, plus a cost $c n$ for the merge phase.

The tree method makes visible where the solution comes from: you draw a tree in which each node is a call, with the own cost of that call (excluding the child calls) written next to it.

For merge sort: at level $0$ there is one node with cost $c n$ ; at level $1$ there are $2$ nodes, each with cost $c (n /2)$ , so the level still costs $c n$ in total; at level $2$ there are $4$ nodes of $c (n /4)$ , again $c n$ in total. Every level costs $c n$ , and there are $lo g_{2} n$ levels (because $n$ halves at each level until it reaches $1$ ):

T (n) = c n \cdot lo g_{2} n + O (n) = O (n lo g n)

For binary search the reasoning is simpler: one node per level, constant cost $c$ per node, and $lo g_{2} n$ levels:

T (n) = c \cdot lo g_{2} n = O (lo g n)

The master theorem formalises this method for recurrences of the form $T (n) = a T (n / b) + f (n)$ , giving the solution based on a comparison between $f (n)$ and $n^{l o g_{b} a}$ without having to redraw the tree every time — useful to know, but understanding why the tree method works remains the most solid way not to go wrong when the professor slightly changes the numbers of the recurrence compared with the example seen in lecture.

The mistakes that cost marks

Confusing $O$ with “the exact time”. $O (n^{2})$ doesn’t mean “takes exactly $n^{2}$ steps”: it means that, from a certain point on, it doesn’t exceed $c \cdot n^{2}$ for some constant $c$ . An algorithm that does exactly $n^{2} /2$ operations is still, correctly, $O (n^{2})$ .
Miscounting dependent nested loops by treating them as if they were independent, instead of summing explicitly (see Gauss’s sum above). Sometimes the final result coincides anyway, sometimes not: the wrong method sooner or later lets you down.
Forgetting the constants when they really matter, that is precisely in proofs with explicit $c$ and $n_{0}$ : there the constants are not thrown away, they are the object of the proof.

Three worked exercises

Exercise 1 — analysing three fragments of code.

// (a)
for (int i = 0; i < n; i++) {
    std::cout << i;
}
// Complexity: O(n) — one loop, n iterations.

// (b)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        std::cout << i << j;
    }
}
// Complexity: O(n^2) — two independent loops, n * n iterations.

// (c)
for (int i = 1; i < n; i = i * 2) {
    std::cout << i;
}
// Complexity: O(log n) — the index doubles at each step.

Exercise 2 — proving that $3 n^{2} + 5 n = O (n^{2})$ .

We have to find $c$ and $n_{0}$ such that $3 n^{2} + 5 n \leq c \cdot n^{2}$ for every $n \geq n_{0}$ . For $n \geq 1$ we have $5 n \leq 5 n^{2}$ , so:

3 n^{2} + 5 n \leq 3 n^{2} + 5 n^{2} = 8 n^{2}

It is enough to choose $c = 8$ and $n_{0} = 1$ : for every $n \geq 1$ , $3 n^{2} + 5 n \leq 8 n^{2}$ . The proof is complete as soon as $c$ and $n_{0}$ are exhibited and the inequality is checked — there is no need to find the “tightest possible” pair, one that works is enough.

Exercise 3 — solving the recurrence $T (n) = 2 T (n /2) + n$ , with $T (1) = 1$ .

With the tree method: level $0$ costs $n$ ; level $1$ has $2$ nodes of $n /2$ each, so again $n$ in total; level $k$ always costs $n$ in total, and there are $lo g_{2} n$ levels before reaching the base cases. So:

T (n) = n \cdot lo g_{2} n + O (n) = O (n lo g n)

It is the same structure as the merge sort seen above — not by chance: the merge sort recurrence is exactly this one, up to the multiplicative constant on the linear term.

Where it leads next

Once asymptotic complexity is solid, the typical next step in the course is data structures (lists, trees, heaps, graphs) and how their choice changes the complexity of operations — a good link, if your course includes it as well, is databases and SQL, where indexes and query plans are a direct application of these same concepts. If the course works in C and you still lack confidence on pointers and dynamic memory, this guide to pointers covers exactly that ground. And if you come from a technical high school path where you have already seen loops and arrays, the post on nested loops and arrays in Year 3 computing shows the same logic one level down — useful for understanding where you are coming from, not for preparing for the university exam itself.

How I work on this topic in lessons

With those who get stuck on complexity, the problem is almost never the definition itself: it is not having yet translated into practice what “finding $c$ and $n_{0}$ ” means, or trusting intuition about nested loops too much without checking it with an explicit sum like Gauss’s. We work on real fragments of code — often those from the exam exercise that blocked you — and analyse them together line by line, before moving on to the formal proofs.

If you are also preparing for numerical analysis, the logic of estimating an error with explicit constants is exactly the same as this proof with $c$ and $n_{0}$ — it is worth seeing them together.

If the same course also has MATLAB, complexity shows up in loop timings: I wrote about it in MATLAB and Simulink for engineering exams. For the sums and limits needed to calculate complexities, practise with the university exam mock tests on calculus (questions in Italian).

The computer science lessons for university students are online and one to one; you will find the general picture of university tutoring on the dedicated page. If you want to talk about it before booking, we are on the contact page.

Algorithm complexity and Big-O notation