This map explains how the calculate the cost of an algorithm: how many operations it does as a function of the size of the data, n, and how it grows when n grows.
The cost is a function of n. Seconds depend on the computer; operations do not.
Press each box to see its explanation. The arrows ← → (or the buttons at the bottom) go to the next one and Esc closes it. Once you have seen it, a ✓ appears; press it to remove it. The boxes with «?» belong to other levels.
This map explains how the calculate the cost of an algorithm: how many operations a program does. Each box has a short explanation and, in some cases, an exercise.
An algorithm is more fast when it does fewer operations.
Press each box to see its explanation. The arrows ← → go to the next one and Esc closes it. Once you have seen it, a ✓ appears.
Year 4 ESO (for the advanced). Simplified version: calculation rules, order with respect to n and binary search. No formal O(·) notation, no algorithm graphs and no operations box.
Fits into: Digitalisation Year 4 (computational thinking: criteria 3.1 and 3.2, logical and efficient algorithms).
Suggested activity: count the operations of a loop and then check with binary search how many steps it takes.
PTD-I · 1st year of Bachillerato. The calculation rules (sequence, conditional and loop), O(·) notation, growth and time graphs, linear search and selection sort are added. Time experiments (ms) stop being the centre: what is measured is the number of operations.
Fits into: Programming and Data Processing I: CEsp1 (analysis and design of algorithms, criterion 1.3 on computational cost) and CEsp3 (efficiency and complexity of operations on data structures).
Suggested activity: with 10⁹ operations per second and n = 10⁶, work out how long linear search (n) and bubble sort (n(n−1)/2) would take, and compare it with the time graph.
PTD-II · 2nd year of Bachillerato. Same content as PTD-I: calculation rules, O(·) notation, growth graphs and the search and sorting algorithms.
Fits into: Programming and Data Processing II: CEsp1 (algorithms and computational thinking).
Suggested activity: compare by hand linear search and binary search with n = 1 000 000 and justify the difference.
The boxes with «?» are hidden at this level: one click reveals them and shows their relation, another opens the window and, after seeing it, another click hides them again. The button 🔗 copies a link with the level and the revealed boxes.
The selector Level changes the map and all the windows. The address keeps the level (?edad=4eso, ptd1 or ptd2) and the revealed boxes (&ver=casos,fonts).
When we say an algorithm is fast, we need to say fast at what. Seconds depend on the computer, the system and what is running. That is why we count operations.
When you compare two algorithms, ask yourself: what grows and by how much?
Computational cost measures the work a program does depending on the size of the data (n. Look at two things: the time (number of operations) and the memory (how much space it takes up).
The computational cost of an algorithm is the number ofelementary operations that does, as a function of the size of the data, n. Seconds depend on the computer; operations do not.
An elementary operation (assignment, addition, comparison or access to a position) costs 1. Count the worst case, which is what guarantees the result for any data.
| Function T(n) | n = 10 | n = 1 000 | n = 1 000 000 |
|---|---|---|---|
| n | 10 | 1 000 | 1 000 000 |
| n² | 100 | 1 000 000 | 1 000 000 000 000 |
Seconds are no use for comparing algorithms. Count operations and look at how grow when n grows.
The size n. All formulas depend on a size, n: the number of data items the algorithm receives. Define n before counting (number of elements, digits or rows, depending on the problem).
A program runs instructions one after another. To calculate the cost, add the instructions. If there is a loop, multiply by the number of times it repeats.
A simple instruction costs 1. A loop multiplies the cost of its body by the number of repetitions.
A program combines four structures. The total cost is calculated by applying a rule to each one.
| Structure | Cost rule | Example |
|---|---|---|
| Simple instruction | 1 | x ← x + 1 → 1 |
| Sequence | sum of the costs | A; then B → T(A) + T(B) |
| Conditional | test + the most expensive path | if … then … else … → 1 + max(T₁, T₂) |
| Loop | iterations × cost of the body | for i from 1 to n: x ← x + 1 → n |
When you do not know which branch of a conditional will run, use the most expensive one: it is the worst case.
The cost of a loop is the cost of its body multiplied by the number of repetitions. One operation goes unnoticed; a million does not.
| Structure | Operations with n = 1 000 | Operations with n = 1 000 000 |
|---|---|---|
| A loop | 1 000 | 1 000 000 |
| Two nested loops | 1 000 000 | 1 000 000 000 000 |
Count how many times the innermost body runs. A loop of n steps makes n operations; two nested loops of n steps make n · n.
Two nested loops are O(n²); a loop, O(n).
A structure that looks simple («it is just a loop») can hide a search inside. Always check what is inside the loop.
A loop repeats its body. The total cost is the cost of the body multiplied by the number of repetitions.
| Structure | Operations with n = 1 000 | Operations with n = 1 000 000 |
|---|---|---|
| A loop | 1 000 | 1 000 000 |
| Two nested loops (n · n) | 1 000 000 | 1 000 000 000 000 |
| Two loops, the second up to i | 500 500 | 500 000 500 000 |
A loop is O(n). Two nested loops are O(n²). Nested loops that go up to i make n(n+1)/2 steps: also O(n²), because we ignore the constant ½.
A structure that looks simple («it is just a loop») can hide a search inside. Always check what is inside the loop.
Bubble sort compares neighbours and swaps them if they are in the wrong order. It repeats passes until it makes no swap. It is the typical algorithm for understanding cost, because everything can be counted.
| n (data) | Comparisons (worst case) | Swaps (average) |
|---|---|---|
| 10 | 45 | 22,5 |
| 100 | 4 950 | 2 475 |
| 1 000 | 499 500 | 249 750 |
| 10 000 | 49 995 000 | 24 997 500 |
Each pass puts the largest value at the end. With n data items, the first pass makes n−1 comparisons, the next n−2, and so on down to 1. In total, in the worst case: n(n−1)/2.
Notice: if you multiply the data by 10, the work is multiplied by 100.
This is O(n²). Comparisons grow like the square of n.
Bubble sort compares each pair of neighbours and swaps those that are out of order. After each pass, the largest value ends up at the end.
| n (data) | Comparisons (worst case) | Swaps (average) |
|---|---|---|
| 10 | 45 | 22,5 |
| 100 | 4 950 | 2 475 |
| 1 000 | 499 500 | 249 750 |
| 10 000 | 49 995 000 | 24 997 500 |
The first pass makes n−1 comparisons, the second n−2, and so on down to 1. Total in the worst case: (n−1) + (n−2) + … + 1 = n(n−1)/2, that is O(n²).
Time graph: time is proportional to the number of operations. With 10⁹ operations per second, 10⁶ operations take 1 ms.
If the list is sorted, you do not need to look at all of it. You look at the middle and discard the half that cannot contain what you are looking for. Each step halves the size.
The list is 1, 2, 3… n: there is no need to store all of it in memory, which is why it can be tested with 1 000 000 000.
| n (data) | Binary steps (worst case) | Linear comparisons (worst case) |
|---|---|---|
| 1 000 | 10 | 1 000 |
| 1 000 000 | 20 | 1 000 000 |
| 1 000 000 000 | 30 | 1 000 000 000 |
Each step makes one comparison and eliminates half. The steps are roughly log₂ n. That is why 1 000 000 000 data items only need 30 steps.
This is O(log n).
Binary search only works if the list is sorted. Sorting it also has a cost.
Binary search looks at the middle of the sorted list and discards the half that cannot contain what you are looking for. Each step divides by 2.
The list is 1, 2, 3… n. Only the steps are counted: there is no need to store it in memory.
| n (data) | Steps (worst case) | Linear search (worst case) |
|---|---|---|
| 1 000 | 10 | 1 000 |
| 1 000 000 | 20 | 1 000 000 |
| 1 000 000 000 | 30 | 1 000 000 000 |
Each step halves the size: after k steps there are n / 2ᵏ elements left. Since n / 2ᵏ = 1 when k = log₂ n, the cost is O(log n).
Binary search only works if the list is sorted. Sorting it also has a cost.
Time graph: time is proportional to the number of operations. With 10⁹ operations per second, 10⁶ operations take 1 ms.
When the data grow, the cost grows at a particular rate. The notation O(·) only keeps this rate and ignores the constants.
O(log n) grows very slowly: when n goes from 1 to 20, it only reaches ≈ 4.3, while O(n) reaches 20.
With small n all the curves look close together; from n ≈ 10 onwards the quadratic separates from the others.
| Function | n = 10 | n = 1 000 | n = 1 000 000 |
|---|---|---|---|
| O(log n) | ≈ 3 | ≈ 10 | ≈ 20 |
| O(n) | 10 | 1 000 | 1 000 000 |
| O(n log n) | ≈ 33 | ≈ 10 000 | ≈ 20 000 000 |
| O(n²) | 100 | 1 000 000 | 1 000 000 000 000 |
O(1): the cost does not depend on n. O(log n): each step divides by 2 (binary). O(n): proportional to n (linear search). O(n log n): typical of good sorting algorithms. O(n²): two nested loops (bubble sort, selection sort).
When n is multiplied by 10: with O(n) the cost is multiplied by 10; with O(n²), by 100; with O(log n), it hardly changes.
Ignore constants and small terms: 3n² + 5n is O(n²).
The order with respect to n explains how the cost grows when the data grows. It is the most important idea in this map.
When n is multiplied by 10, an O(n) cost is also multiplied by 10, but an O(n²) cost is multiplied by 100.
If the cost is O(n), the work grows at the same rate as the data. If it is O(n²), with double the data the work quadruples.
What matters is how it grows, not the exact number of operations.
The same algorithm can take more or less time depending on the data. That is why the analysis distinguishes three cases: best, average and worst.
| Case | Bubble sort | Binary |
|---|---|---|
| Best | n−1 comparisons (already sorted list) | 1 step (the middle is the one searched for) |
| Average | ≈ n²/2 comparisons | ≈ log₂ n steps |
| Worst | n(n−1)/2 comparisons | ⌊log₂ n⌋ + 1 steps |
If the ratio is close to 2, the growth is roughly linear; if it is close to 4, quadratic. Browser noise means it is not exact: that is why the median of 3 repetitions is taken.
To evaluate an algorithm, look at the data of worst case (the ones that make it work hardest), but also the average case, which is usually the most common.
A single measurement of a particular case does not tell you which is the worst. Analyse the case and then measure.
Linear search looks at the elements one by one until it finds what you are looking for. It is the simplest method and serves as a reference for comparing with binary search.
Each element is compared with the value searched for until it is found or the end is reached.
| Case | Comparisons | With n = 1 000 000 |
|---|---|---|
| Best (it is the first) | 1 | 1 |
| Average (it is in the middle) | n / 2 | 500 000 |
| Worst (it is the last one or it is not there) | n | 1 000 000 |
The cost is O(n): each element is examined at most once.
When you give a cost, say which case is: the best, the average or the worst.
Time graph: time is proportional to the number of operations. With 10⁹ operations per second, 10⁶ operations take 1 ms.
Selection sort finds the minimum of the unsorted part and puts it in front. Repeat until the whole list is sorted.
The first pass finds the minimum among n elements (n−1 comparisons) and puts it in the first position. The next one searches among n−1 elements, and so on until the last one.
| n (data) | Comparisons (always) |
|---|---|
| 10 | 45 |
| 100 | 4 950 |
| 1 000 | 499 500 |
Total: (n−1) + (n−2) + … + 1 = n(n−1)/2, that is O(n²) in all cases. It makes at most n−1 swaps.
Selection always makes the same comparisons; bubble sort can stop earlier if the list is already sorted.
Time graph: time is proportional to the number of operations. With 10⁹ operations per second, 10⁶ operations take 1 ms.
Insertion sort takes each element and places it in its correct position within the already sorted part.
In the worst case (reversed list) makes n(n−1)/2 comparisons: O(n²). In the best case (already sorted list) it only makes n−1: O(n).
Insertion is fast when the list is already almost sorted.
Merge sort splits the list in half, sorts each half and then merges them.
Each level of divisions takes n steps and there are log₂ n levels. The cost is O(n log n) in all cases.
For large lists it is much faster than bubble sort.
Measuring is easy to get wrong. These are the most common mistakes, and how to avoid them.
Before saying that an algorithm is faster, ask yourself: with what data, on which machine and how many times I measured it.
Read each situation and choose which concept explains the case. If you choose one that is also there but is not the main one, we will tell you.
A program adds 1 000 000 numbers inside a loop. Which concept explains why the cost is high?
A program adds 1 000 000 numbers inside a loop. Which concept explains why the cost is high?
You look for the number 42 in a sorted list of a million numbers. You look at the middle, discard half and, in about 20 steps, find it. Which algorithm is this?
An algorithm goes through the list comparing neighbours and swapping them. With the reversed list it makes n(n−1)/2 comparisons. Which algorithm is it?
An algorithm takes 4 times as long when you double the data. Which concept describes how its cost grows?
You look for a number in an unsorted list of n elements and compare it with each element until you find it. Which algorithm is this?
An algorithm finds the minimum of the unsorted part and puts it in front. It makes n(n−1)/2 comparisons even if the list is already sorted. Which algorithm is it?
This map brings together classic concepts from algorithm analysis and the curriculum objectives of the Balearic Islands. Here you can check them and go further.