37: Big-O Notation. Take It To The Limit.

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 geom