(561) 600-0707 contact@takeupcode.com
Select Page

Big-O notation gives you the ability to describe how fast your code will run if given a large problem. It remains relevant because it doesn’t base anything on how fast or slow your computer actually is. Computers get faster all the time and there are so many different capabilities from a simple micro controller, to an average laptop, to the largest super-computer. Big-O notation works on all of these because it doesn’t care what type of processor you have. It just looks at the steps needed to solve the problem and how they scale as the problem gets bigger.

This episode also introduces two new terms, algorithms and asymptotes.

An algorithm is just the set of steps that a program takes to turn some input into some output. There are different ways that problems can be solved and some of them are much more efficient than others.

An asymptote is a line that in geometry is used to describe how some curve will converge upon. The curve may start out far from the line but will get closer. The curve might pass through the line and for a while get farther away again but it will eventually start approaching the line again. The curve will keep getting closer to the line. Eventually all the initial deviations will fade away and the line will dominate everything.

That’s how Big-O notation works. As the problem gets bigger, the speed of one computer vs. another become less and less of an issue until only the line remains. The line represents the steps that the code is taking to solve the problem. And some approaches to the problem will have asymptotic lines that are much faster than others as the problem size becomes large enough.

Listen to the full episode or read the full transcript below.

## Transcript

Think of it like this. A car has a specific top speed that depends on the type of car and what modifications have been made to it. A computer is like a car in this sense because the speed that a computer can run code depends on the type of processor and what other modifications have been made. Big-O notation is not concerned about how fast any specific car or computer can go but how fast can your code can go.

The speed of a car also depends on the skill of the driver. This doesn’t mean that a racing champion will win a race in a old clunker. But it’s more like how given any specific car, a racing champion will be able to drive that car faster around a course than somebody with less skill. You code is more like the driver of a car than the car itself because it can run on different computers just like a driver can drive different cars. Asking how long it will take a champion driver to complete a course when the type and condition of the car can change is meaningless.

Here’s where programming has an answer. With Big-O notation, asking how long it will take to run your code actually means something even without knowing anything at all about the speed or capabilities of the computer. You can compare code that was written 50 years ago with code from today and get value from that comparison. And you can do this even though a handheld calculator today has more power than the best computers back then.

How is it possible to ignore the speed of a computer and focus on just what the code does? It’s because when examining an algorithm. And let me stop here for a moment. An algorithm is not the same thing as a logarithm even though both words end with a “rithm” sound. An algorithm is just a fancy word for how something is done. In other words, what steps need to be taken to solve a problem. An algorithm is also concerned with what input is provided and by solving the problem, it produces some form of output. Okay, so when examining an algorithm, we can ignore specific factors such as the speed of the computer because we take the problem to the largest size imaginable. This is called a limit and the study of problems at this scale means we’re studying the asymptotic efficiency.

An asymptote in geometry is a line that a curve gets closer and closer to as the curve and the line stretch out to infinity. The curve might sometimes cross the line and momentarily get a little farther away. But it will eventually get closer to the line again. If not, then the line doesn’t represent an asymptote. The line becomes the limit of the curve. What this means is the running time of an algorithm may be affected drastically by specifics such as how fast the machine happens to be when the problem size is small. But as the problem size becomes larger, the limit will just dominate everything and nothing else matters anymore.

Think about it this way. A mountain is big and heavy, right? Full of rock. Now imagine a computer big and fast enough to eat that mountain for breakfast. I know, computers don’t eat rocks. Never mind, this one does. That’s a fast computer and compared to one from 50 years ago, the old computer would be lucky to finish a handful of sand. It seems like the speed of the computer really makes a difference here. But let’s take it to the limit. Because while a mountain is big, there’s things bigger still. What if we gave it an entire continent? How about a small moon? The earth itself? The thing about lines and curves that stretch to infinity is they can get pretty far out there. If we take this to the limit of all the stars, planets, and matter in the universe, then the difference between the two computers becomes so insignificant now. What seemed like a huge difference at first has ended up with both computers identical.

I have another example for you but before that, let’s take a moment to thank our sponsor.