What 'fast' really means

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

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 data gets big enough. The hardware buys you a constant multiplier. The algorithm decides the shape of the growth, and growth always wins.

So if it isn't the computer, what is it? It's the number of steps your code takes. Every single time your program looks at a piece of data, compares two things, or does a little arithmetic, that's one step of work. Fewer steps means faster code. That's the whole game. Everything in data structures and algorithms - every clever trick in this course - is ultimately about doing fewer steps to get the same answer.

And here's the freeing part: you don't need to time anything with a stopwatch. You count. If you can count how the steps grow as the input grows, you can predict whether code will fly or freeze - before you even run it. That skill is what separates people who guess from people who know.

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.

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.

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.

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.

Say hello to O(n)

When the number of steps grows in a straight line with n - n items means roughly n steps - we say the algorithm runs in O(n), read aloud as 'oh of n' or 'order n'. That capital O is Big-O notation, and it is simply shorthand for one question: as the input grows, how does the work grow with it?

O(n) is the honest, everyday speed of 'look at everything once'. Scanning a list, summing numbers, finding the largest value - all O(n). It is not slow, and it is not something to be ashamed of. But it carries a promise you must respect: make the input a million times bigger, and the code does a million times more work. Sometimes that's completely fine. Sometimes, as the very next lesson shows, it's a catastrophe - and sometimes, as the lesson after that shows, we can do breathtakingly better.

The cost ladder

O(n) only means something once you can compare it to its neighbours. So here is the single most important picture in this entire chapter: how many steps four different kinds of algorithm need to finish the same job on a list of one million items. Read it slowly.

Why this is the lesson everything rests on

Look at that ladder one more time, because the rest of the course lives inside it. Almost every algorithm you'll learn is a story about moving down a rung - taking something that looks like O(n squared) and finding the structure, the sorted order, or the single clever pass that drops it to O(n) or even O(log n).

You now hold the one tool that makes all of that legible: you can look at code, count how its work grows, and name its cost. That is the literacy the whole subject is written in. Everything from here - arrays, recursion, sorting, trees, graphs - is just new ways to climb down this ladder.