What 'fast' really means

Real execution, step by step. Press play or scrub with the controls - every variable and array index updates live.

Start here: what this lesson is for

Welcome to the first lesson of the course. Before anything technical, here is what you are about to learn and why it comes first.

By the end of this page you will be able to look at a piece of code - code you have never seen before, written by someone else - and say roughly how expensive it is. Not by running it. Not by timing it. Just by reading it and counting.

That single skill is the foundation of everything else in this course. Every later chapter - sorting, searching, trees, graphs - is really a collection of tricks for doing less work. If you cannot measure work, none of those tricks will feel like anything more than trivia to memorise. Once you can measure it, they start to feel obvious.

You do not need any prior knowledge. If you can read a basic loop, you have enough to follow every word below.

Fast code isn't a fast computer

Here's the first surprise of this whole course, and it catches almost everyone: whether code is 'fast' or 'slow' has almost nothing to do with how expensive your computer is. A brilliant algorithm on a cheap phone will crush a clumsy one running on a supercomputer, every time, as soon as the amount of data grows.

That sounds like an exaggeration, so let's make it concrete. Imagine two programs that both search a list of names. The first checks names one at a time. The second uses a smarter method you will meet in lesson three. On a list of ten names, both finish instantly and you would never tell them apart. On a list of ten million names, the first takes several seconds and the second still finishes instantly - on the same machine, in the same language.

So buying a machine twice as fast makes your code twice as fast, which sounds good until you realise the data you are handling might grow ten times. Then you have lost, badly. The method scales; the hardware does not.

This is why professional engineers talk about algorithms rather than hardware, and it is why this lesson exists before any data structure does.

What exactly counts as one step?

If we are going to count steps, we need to agree on what a step is. The good news is that the definition is deliberately loose, and that looseness is a feature rather than sloppiness.

A step is any single small action that takes roughly the same amount of time no matter how big your data is. Comparing two numbers is a step. Adding two numbers is a step. Reading one item out of an array is a step. Assigning a value to a variable is a step.

What is not one step is anything that secretly loops. Reading one item from an array is one step; reading every item is one step per item. Calling a method that itself walks a list is not one step - it is however many steps that method takes. This is the most common early mistake: treating a method call as free because it is a single line of code.

Notice we are not measuring seconds. One step might be a nanosecond on your laptop and three nanoseconds on a cheap phone, and we simply do not care. We are counting how many steps, because that number is a property of the algorithm itself and stays true on any machine, in any language, in any year.

Watch it count

Scroll back up to the animation for a second - it's a real Java method, a linear search, hunting through a row of numbers for the value 16. 'Linear' just means it walks in a straight line, one box after another, left to right. Press play and physically count the checks. It looks at 4, then 8, then 15, then 16 - found it, on the 4th look.

Now let's look at the code that produced it. Do not worry if Java is not your language; read it as instructions in English. The loop starts at the first box, and each time round it asks one question: is this the number I want?

Here's that same array as a picture. The search starts at index 0 and steps right until the value it's holding matches the target. Each box it opens is one step.

int linearSearch(int[] numbers, int target) {
    for (int i = 0; i < numbers.length; i++) {   // one step per box opened
        if (numbers[i] == target) {
            return i;                            // found it - stop early
        }
    }
    return -1;                                   // walked the whole row, no match
}

int[] numbers = {4, 8, 15, 16, 23, 42};
System.out.println(linearSearch(numbers, 16));

3

Best case, worst case

Our search found 16 in four steps. But that number depends entirely on what we searched for. Ask for the very first value, 4, and it finishes in a single step - the best case. Ask for 42, the last one, and it must open every box. Ask for a value that isn't there at all, say 99, and it still has to check all six before it can honestly say 'not found'.

That last situation - the input that forces the most work - is the worst case, and it is the one professionals care about most. Anyone can look fast on a lucky input. We judge an algorithm by how it behaves when the luck runs out, because that's the guarantee you can actually build on.

There is a third measure, the average case, and it is exactly what it sounds like: the cost over typical inputs rather than the luckiest or unluckiest. It is genuinely useful, but it is also harder to reason about, because it requires you to know what 'typical' means for your data. When people quote a single cost without saying which they mean, they almost always mean the worst case - and so will we, unless we say otherwise.

For a list of n items, a linear search does at most n steps in the worst case. Double the list, and you double the work. Make it ten times longer, and you do ten times the work. The steps grow in a perfectly straight line with the size of the input - and that straight-line growth has a name.

Don't take our word for it - make the code count for you. Add a counter, run the same search three times, and read the three numbers:

int stepsToFind(int[] numbers, int target) {
    int steps = 0;
    for (int i = 0; i < numbers.length; i++) {
        steps++;                                // count every box we open
        if (numbers[i] == target) return steps;
    }
    return steps;                               // opened them all, found nothing
}

int[] numbers = {4, 8, 15, 16, 23, 42};
System.out.println(stepsToFind(numbers, 4));    // best case
System.out.println(stepsToFind(numbers, 42));   // worst case
System.out.println(stepsToFind(numbers, 99));   // not there at all

1
6
6

Say hello to O(n)

Engineers write that straight-line growth as O(n), said out loud as 'oh of n' or 'order n'. It is not as intimidating as it looks. The n is the size of your input, and the whole expression is a short way of saying: the work grows in step with the input.

The capital O is doing one specific job - it means 'grows no faster than'. It deliberately throws away detail you should not be relying on, and knowing what it throws away is what makes it usable.

It throws away constants. Code that does 3 steps per item is O(n), and so is code that does 1 step per item. The first is three times slower, and Big-O does not care, because tripling is a fixed penalty while growth is unbounded.

It throws away smaller terms. Code that does n steps and then another 50 steps is still O(n). Once n is a million, the 50 has stopped mattering.

This feels like cheating the first time you meet it. It is not: it is a deliberate choice to describe the shape of the growth rather than its exact value, because shape is what still holds true when your data is a thousand times bigger.

// all three of these are O(n) - the SHAPE is the same

for (int x : items) sum += x;                            // n steps

for (int x : items) { sum += x; max = big(x); min = small(x); }   // 3n steps

for (int x : items) sum += x;                            // n + 50 steps
for (int i = 0; i < 50; i++) warmUpCache();

n = 1,000       n steps 1,000    3n steps 3,000    n+50 steps 1,050
n = 1,000,000   n steps 1.0M     3n steps 3.0M     n+50 steps 1.000050M

            as n grows, the 3x stays 3x - and the +50 disappears

The other shapes you will meet

O(n) is one shape among a handful you will meet constantly. You do not need to memorise them today - every one gets its own lesson later - but seeing the family now makes the rest of the course feel like a map rather than a maze.

O(1), constant time. The work does not depend on the input size at all. Reading the fifth item of an array takes the same time whether the array holds ten items or ten million. This is the best possible shape.

O(log n), logarithmic. Every step throws away half of what is left. A million items takes about twenty steps. This is nearly as good as O(1), and lesson three is entirely about it.

O(n), linear. What we have been doing. Look at everything once.

O(n log n), linearithmic. The cost of a good sort. Slower than linear, but close enough that it is considered efficient.

O(n squared), quadratic. Usually a loop inside a loop - for every item, do something with every other item. Fine at small sizes, catastrophic at large ones, and the subject of lesson two.

Counting a loop, step by step

Let's turn this into something you can actually do, because reading about counting is not the same as counting. Here is a method that works on any piece of code you meet.

First, find the loops. Code with no loops and no method calls that hide loops is O(1) - it does a fixed amount of work.

Second, for each loop, ask how many times it runs in terms of n. A loop from 0 to n runs n times. A loop that doubles its counter each round - 1, 2, 4, 8 - runs about log n times.

Third, if one loop sits inside another, multiply their counts. If they sit one after the other, add them and keep only the bigger, because addition of different shapes is dominated by the larger one.

That is the whole technique. Everything else is practice.

// A: no loop at all
int first(int[] a) { return a[0]; }

// B: one loop over n
int sum(int[] a) {
    int total = 0;
    for (int x : a) total += x;
    return total;
}

// C: a loop INSIDE a loop - multiply
boolean anyDuplicate(int[] a) {
    for (int i = 0; i < a.length; i++)
        for (int j = i + 1; j < a.length; j++)
            if (a[i] == a[j]) return true;
    return false;
}

// D: two loops one AFTER the other - add, then keep the bigger
int sumThenMax(int[] a) {
    int total = 0, max = a[0];
    for (int x : a) total += x;                 // n
    for (int x : a) max = Math.max(max, x);     // n
    return total + max;                         // n + n = 2n, still O(n)
}

A  no loops                 -> O(1)
B  one loop over n          -> O(n)
C  loop inside a loop       -> O(n squared)
D  two loops in sequence    -> O(n) + O(n) = O(n)

Why this is the lesson everything rests on

You now have the one tool the rest of this course keeps using. Every algorithm you meet from here on is an answer to the same question: can we get this same result while doing less work?

Lesson two takes the loop-inside-a-loop from example C and shows exactly why it becomes unusable, using numbers you can feel. Lesson three shows the opposite - an algorithm that throws away half the problem at every step, and finds one item among a million in about twenty looks.

Before that, one honest caveat. Big-O is about growth, not about speed on a particular day. An O(n squared) algorithm can genuinely beat an O(n log n) one on twenty items, because the constants Big-O discards are still real. That is not a flaw in the theory; it is a reminder that these are two different questions. Big-O tells you what happens as your data grows - and data almost always grows.

If you take one sentence from this lesson, take this: you can predict performance by counting, before writing a line of code. That is the difference between guessing and engineering.