Call search([4, 8, 15, 16, 23, 42], 16) - a new frame is pushed onto the call stack.
primitives are shown in Variables.
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: 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 on a supercomputer, once the data gets big enough.
So if it's not the computer, what is it? It's the number of steps. Every time your code looks at a piece of data, that's one step of work. Fewer steps, faster code. Our entire job in this course is learning to count those steps - and then to do fewer of them.
Look at the animation above. It's a Java method searching a list of numbers for the value 16. Press play. Watch how it checks the boxes one at a time, left to right. Count them. That count - not the clock - is what we care about.
Imagine it like this: Looking for your friend in a cinema by walking up the rows one seat at a time. It doesn't matter how fast you run - what matters is how many seats you have to check.
- algorithm
- - a fixed recipe of steps that turns an input into an answer
- step
- - one unit of work - here, looking at one item in the list
Best case, worst case
Our search checked a few boxes before it found 16. But what if we'd searched for the very first number? One step - done instantly. And what if we'd searched for a number that isn't there at all? Then it has to check every single box before giving up.
That last one - the number that forces the most work - is the WORST case, and it's the one we care about most. Anyone can look fast on a lucky input. We measure algorithms by how they behave when luck runs out.
For a list of n items, this search does at most n steps in the worst case. Double the list, double the work. Ten times the list, ten times the work. The work grows in a straight line with the size of the input. We have a name for that.
- Best case: the answer is right at the start - 1 step
- Worst case: the answer is missing or last - n steps
- We judge algorithms by the worst case, not the lucky one
- n
- - the size of the input - how many items you're working with
- worst case
- - the input that forces the most steps; the honest measure of cost
This is O(n)
When the number of steps grows in a straight line with n - n items means about n steps - we say the algorithm is O(n), read out loud as 'oh of n' or 'order n'. That capital O is 'Big-O', and it's just shorthand for 'how does the work grow as the input grows'.
O(n) is the honest, everyday speed of 'look at everything once'. Scanning a list, adding up numbers, finding the biggest value - all O(n). It's not slow. But it does mean: if your list gets a million times bigger, your code does a million times more work. Sometimes that's fine. Sometimes, as you'll see next lesson, it's a disaster - and sometimes, as you'll see after that, we can do dramatically better.
Imagine it like this: O(n) is reading every page of a book to find one word. A 1,000-page book takes ten times longer than a 100-page one. Fair, predictable, and sometimes far too slow.
- Big-O
- - notation for how an algorithm's work grows as the input grows
- O(n)
- - linear time - the work grows in step with the input size
Check your understanding
0/3 answeredQ1What mainly decides whether an algorithm is 'fast' or 'slow'?
Q2A linear search over n items - how many steps in the WORST case?
Q3Why do we measure the worst case instead of the best case?