Why Better Algorithms Beat Fast Hardware

0:00You're listening to a podcast right now, driving, working out, walking the dog. If you're into podcasts, chances are you have something to say too. With RSS.com, starting your own is free and easy. Upload an episode, and we distribute it to Apple podcasts, Spotify, Amazon Music, and hundreds more. Track your listeners, see where they're from, and start earning from ads like this. Even with just 10 listeners a month. If you've been thinking about starting a podcast, this is your sign. Start free at RSS.com. Imagine you were standing in the middle of a massive, completely disorganized library. Like just books scattered absolutely everywhere on the floor. Exactly. Millions of books, just everywhere. And you were looking for one specific title. Now you could be the fastest runner on earth, right? Like a human sports car. But if your strategy is literally just running down the aisles, looking at every single spine one by one, you are a slow walker who, you know, just took a few minutes to check

1:05a master index is going to beat you to that book every single time. Because the physical speed of the runner doesn't actually matter if the fundamental method they're using to search is flawed. You know, you just can't outrun a bad strategy. You really can't. And welcome to the deep dive. I'm your host. And that disorganized library is exactly the core of what we're unpacking today. I'm really excited for this one. I've spent years studying this exact topic. So it's going to be fun to dig in. Awesome. So we are pulling from a really comprehensive set of source material today centered around this deeply detailed Wikipedia article on the analysis of algorithms. Right. And the mission of this deep dive for you listening is to basically figure out how computer scientists actually measure if an algorithm, which is, you know, the fundamental strategy your computer takes to solve a problem. If that algorithm is actually efficient because it's a lot more complicated than just hitting a stopwatch. It is. And we're going to see exactly why simply going out and buying a faster computer is often the absolute worst way to fix low code.

2:07Okay. Let's unpack this. Efficiency in computer science, like you said, isn't just about stopwatches. No, not at all. It is usually about finding a mathematical function, right? Like a function that links the size of the input you're giving the computer to the number of steps that has to take or the amount of memory storage it requires. Yeah, because an algorithm is really just a recipe. Okay. Recipe. Right. It's a specific set of instructions. And what analysts really need to know is what happens to those instructions when the problem gets bigger? Oh, I see. Like scaling up. Exactly. Yeah. If we go from searching a small bookshelf to searching the Library of Congress, does the time it takes to follow that recipe grow by just a little bit or does it suddenly take, you know, an absolute eternity? Right. Let's start with a really striking visual from our source material that perfectly captures this difference in growth. Imagine you are looking for a specific name in a sorted list of, let's say, 33 items. Just 33. Pretty small. Super small. Let's say you're looking for the name Morin, Arthur.

3:09If you use what's called a linear search, which is the bad way, right, the bad way, which basically means starting at the top and checking every single name one by one, uh, completely ignoring the fact that the list is already in alphabetical order. Yeah. Just brute forcing it. Exactly. It takes 28 check steps to finally find him in that list of 33. And well, 28 steps for 33 items doesn't sound entirely catastrophic to a human, like you could do that in a minute, right? But in the computing world, that's wildly inefficient. If you switch your strategy and use a binary search algorithm, instead, it only takes five steps. Like, five steps instead of 28? Just five. Wow. Visualize how that works for you, listening. Binary search actually takes advantage of the list being in alphabetical order. It, um, it jumps right to the middle of the list and asks, is Morin before or after this middle name? Exactly. And let's say it's before it immediately throws away the entire back after the list. Then it goes to the middle of the remaining games, ask the same question, cuts the list in half again, and just repeats that.

4:11Yeah. The underlying mechanism there is having mathematically theoretical analysis shows that for a list of size n, a binary search takes, at most, the base two logarithm of n steps. Okay. Base two logarithm. Just so we are totally clear here, that's basically just the mathematical term for that having process, right? That's right. Because you are repeatedly dividing the problem into the number of steps grows logarithmically, rather than linearly, whereas a linear search can take up to n steps. So if the list is a million items long, it might take a million checks, which is brutal. And this stark difference in mechanisms brings us to this massive trap that, according to the source, even experienced programmers and massive tech companies still fall into, lying on empirical testing. Yes. The empirical trap. So by empirical testing, the force basically means just running the code in the real world, like literally hitting go on a stopwatch to see how fast the program finishes. Right. And the problem with that is algorithms are actually platform independent.

5:13Okay. What does that mean exactly? The pure logic of a binary search can run on any machine. It can be written in any programming language. Because of that real world benchmark tests where you just time the program can be incredibly deceptive. Because the hardware gets in the way. Exactly. The hardware muddies the waters. The source provides a brilliant example to prove this, actually. Let's put two computers against each other. Okay. I love this example. We have computer A, which is this state-of-the-art lightning fast machine, top-of-the-line processor, incredible specs. But we are going to force it to run that slow, linear search algorithm. So it's the human sports car checking every single book spine one by one. Yes. Perfect analogy. And then we have computer B. Now computer B is a much slower, older machine, just a total clunker. Right. But computer B gets to run the highly efficient binary search algorithm. Okay. If we do a benchmark test on a tiny list, say just 16 items, computer A finishes in

6:14eight nanoseconds. Computer B takes 100,000 nanoseconds. Okay. So if you're an engineer just looking at the results of that empirical test, you'd say, wow, computer A is absolutely crushing it. I mean, it's thousands of times faster by more of computer A. You would jump to the conclusion that computer A is running a far superior system, and you would be dramatically wrong. Bermanically wrong. Because computer A is exhibiting a linear growth rate. This runtime is directly proportional to the input size. If you double the length of the list, you just double the time it takes. Right. Computer B, however, exhibits that logarithmic growth rate we talked about. Because every single time it takes a step, it wipes out half of the remaining problem. Having it. Yeah. So if you exponentially quadruple the input size, it's runtime only increases by a tiny constant amount. Okay. Here's where it gets really interesting. Keep ramping up the size of that list. That massive gap starts to close, right? By the time we feed both computers a list of 1 million items, they actually tie. They do. They both take exactly 500,000 nanoseconds.

7:15Yeah. That tie at 1 million items is the tipping point. And the list obviously doesn't have to stop at a million. Let's say we scale up the input size to about 63 trillion items. Okay. 63 trillion. That's 63.7, 7, 2 times 10 to the 12th power. Computer B are slow clunker with the smart algorithm, finishes searching that massive list in just 1.375 milliseconds. Okay. Wait. So computer B takes just over 1 millisecond. What about computer A? The state-of-the-art machine checking, 1 by 1. Computer A will take exactly 1 year to finish. A whole year. Seriously, the math actually works out to a full year. It worked out perfectly to a year. Because to check 63 trillion items, literally at the speed it was going, the time just scales directly. That is insane. Right. It proves, without a shadow of a doubt, that algorithm design completely trumps hardware speed when you are operating at scale. A faster processor just cannot save you from a linear growth rate. Okay. So if empirical testing is a trap, right, and if you can't trust a stopwatch because hardware

8:16muddies the waters, how on earth did computer scientists actually figure out a way to prove one algorithm was better than another? Well, they had to step away from physical testing completely and use pure mathematics. Specifically, what the source text calls asymptotic estimates. Asymptotic estimates. Yeah, they allow us to estimate the complexity of an algorithm for an arbitrarily large input. Basically, we ask, what happens to the math when the data approaches infinity? Ah, okay. When things get infinitely big. Exactly. To do this, computer scientists use notations like Big Omega, Big Theta, and the most famous one, Big O notation. The term analysis of algorithms and much of this methodology was actually coined by the legendary computer scientist, Donald Neuth. Right, Donald Neuth. Okay, so Big O notation. You know the way I finally wrapped my head around this was thinking about describing the absolute worst case scenario for a road trip. Oh, I like that. Yeah, like, if you're going to visit a friend and you tell them, look, at worst it will take me three hours to drive there, you are placing an upper limit on the time.

9:20Right, an upper bound. Exactly. If there's traffic or a detour, it won't take more than three hours. In mathematical terms, Big O says that beyond a certain point, the runtime of an algorithm will never be larger than a constant, what's called it, C, multiplied by a specific mathematical function of the input size, F of N. Right. It just places a hard ceiling on how bad things can get as the data grows. That road trip analogy perfectly captures the spirit of the upper bound. For example, let's look at sorting data. If you are sorting a list of numbers using an algorithm called insertion sort, it's worst case runtime grows quadratically. Quadratically. Yeah. So we say it is of order O of N squared. Let me make sure I'm picturing insertion sort correctly. That's kind of like organizing a hand of playing cards, right? Yes, exactly. They can pick up a new card and you have to compare it to every single card already in your hand to find exactly where it goes. That's the exact mechanism. If you have N cards, you are doing roughly N comparisons for every single one of those

10:21N cards, hence N times N or N squared. If you double the amount of data, the time it takes quadruples. If you triple the data, the time increases by nine times, which, as we saw with the linear search versus binary search, is a growth rate you really want to pay attention to because an O of N squared algorithm is going to hit a wall very fast. It will. It really will. Now, while big O is incredibly useful for expressing that worst case road trip scenario, our sources make sure to note it can express average cases too. Oh, interesting. So it's not just the worst case, right? Take another sorting algorithm, quicksort. It's absolute worst case scenario is also O of N squared. But because of how it divides data on average, its runtime is actually O of N log N, which is better, which is a much, much flatter, faster curve. Okay. So we have this theoretical language to describe growth. We know O of N squared is generally worse than O of N log N at scale because we were looking

11:22at the shape of the mathematical curve. This raises an important question, though. How can we mathematically tally up the steps an algorithm takes to build these curves if we haven't even defined what a single step actually is in the map? Uh, right. Good point. Because if we are throwing away the stopwatch and ignoring the computer's actual hardware, what are we even counting? Exactly. Like a step for a massive supercomputer is very different from a step for, you know, a smart fridge. Completely different. So for this theoretical analysis to correspond usefully to actual runtime, we have to guarantee that the time required to perform a step is bounded by a constant. To standardize this, computer scientists generally use two different cost models. Okay. Cost models. The first is the uniform cost model, sometimes called the unit cost model. This model assigns a constant cost of one to every single machine operation, regardless of the size of the numbers involved. Hold on a second. Let me push back on that. Sure. So under this uniform cost model, you're saying adding one plus one takes the exact same

12:23amount of time as adding two numbers that each have a billion digit under that model. Yes. But that seems physically impossible. I mean, a computer actually has to process all those extra digits. That feels completely unrealistic for massive computations. You've hit on the exact flaw of the uniform cost model. It is physically impossible to process a billion digits in the same time it takes to process one. The logic gates in a computer require more time to process more bits of information. This assumption of constant time is a simplification, and you're right. It's not always warranted, which is exactly why the second model exists, the logarithmic cost model. Okay. That sounds like it counts for the size. It does. The logarithmic cost model assigns a cost to every machine operation that is proportional to the number of bits involved. Oh, bits, sir. Yeah. A billion digit numbers would cost significantly more theoretical steps than adding one plus one. That makes perfect sense. So if the logarithmic model is more accurate to reality, why wouldn't they just use it all the time?

13:23Well, because it is incredibly cumbersome to calculate way too much math, in daily programming, the numbers we deal with usually fit comfortably within standard fixed memory sizes, like a 32-bit integer or a 64-bit integer, because the physical size of the numbers is capped by the system, pretending they all take the same constant time doesn't actually skew the mathematical results enough to matter. So it's just practical. Yeah. The uniform model is good enough for standard software. The logarithmic model is really only employed when absolutely necessary. So what's a scenario where it's absolutely necessary, like when do you have to use it? The analysis of arbitrary precision arithmetic, a prime example is cryptography. Oh, like security stuff. Exactly. So you are encrypting secure data like banking information over the internet. You aren't working with normal 10 digit numbers. You are working with astronomically large numbers with hundreds or thousands of digits, just to make it impossible for hackers to guess them.

14:25Wow. And the computer has to break those massive numbers into smaller chunks just to add or multiply them. In those cases, the size of the number dramatically impacts the time it takes to compute. So using the logarithmic cost model is essential to get an accurate O notation there. So for everyday analysis, we just stick to the uniform cost model, assuming each basic step takes one unit of time. So assuming that uniform model, how do we analysts actually peek under the hood and tally up the steps in a piece of code? They evaluate the runtime complexity by looking at the structure of the algorithm itself. Usually analysts will break down a piece of pseudocode. Yeah. Which is like a simplified human readable version of the code. And they assign discrete time units to the different instructions. They might say step one takes time t1, step two takes t2, and so on. Okay. That seems simple enough. You just read down the list and add up all the t's. It is simple until the code loops, especially nested loops when you have a loop running inside another loop. Oh.

15:25That's where the math gets tricky and where the real runtime cost of an algorithm usually hides. Okay. Let me make sure I'm picturing this nested loop math correctly. Is it kind of like a handshake line at a party? Okay. Let's hear it. Let's say the party is our outer loop. The total number of people at the party is in. Right. The first person walks into the room and there's only one person to shake hands with. So one handshake. That's the inner loop running once. Yeah. Then the second person walks in and now there are two people in the room. So they have shake two hands. The third person shakes three hands. And this just keeps escalating until the last person person and walks in and has to shake in hands. It's a brilliant way to visualize it because the inner loops iterations grow exactly like that sequence and arithmetic progression. It's one plus two plus three all the way up to n. So if we want to know the total time that inner loop takes like the total number of handshakes at the party, we have to add all those escalating numbers together. And luckily mathematics gives us a shortcut formula for adding up an arithmetic progression.

16:28The sum of that entire sequence factors out to one half times the quantity of n squared plus n. Okay. So in formula terms, that's one half times n squared plus n. Right. And when we map out the entire algorithm adding the constant times for t1, t2, the test to see if the outer loop should keep running and this newly factored inner loop, we end up with a very long messy polynomial equation. Sounds messy. But here is the crucial takeaway for anyone evaluating complexity. The highest order term dominates the growth rate. The highest order term, meaning like the part of the equation with the biggest exponent. Yes. In our handshake equation, the highest order term is the n squared. As n, the size of our data gets larger and larger, that n squared part of the math grows so massively that it entirely swallows all the smaller terms and the constant factors. It just dwarfs them. Exactly. The linear n terms, the one halves, the t1s, they all become statistically insignificant. Because if n is a million, a million squared is a trillion, and adding a few extra million

17:32on top of a trillion from the other parts of the equation doesn't really change the trajectory of the curve. Not at all. We can mathematically prove that the function's growth is bounded by that n squared. Therefore, the algorithm's runtime order is officially declared to be o of n squared. We've proven it theoretically, mapping the code directly to a curve without ever needing a physical stopwatch. So what does this all mean? We've built this entire theoretical framework on the assumption that data approaches infinity. Right? That's why Big O works. Because at infinity, n squared gets so unimaginably huge, it just swallows everything else. Yes. That's the theory. But we don't live in an infinite world. We certainly do not, and that introduces a massive real world plot twist in the analysis of algorithms. Plot twist. Yeah. This is on asymptotic performance, what happens as things get unimaginably large. But real world data is practically always limited in size. Because it's limited by the physical constraints of addressable memory, right?

18:32Yeah. Our computers only have so much RAM to hold data in the first place. Precisely. On a 32-bit machine, your limit is usually four give-a-bites, which is the strict technical term for how computers measure a gigabyte based on powers of two. On a modern 64-bit machine, the addressable limit is 16-x-bites. Now, 16-x-bites is a staggering amount of memory, but it is deeply, physically finite. Right. It's not infinity. And because our data cannot actually reach infinity, an incredible thing happens to the math. The constant factors suddenly matter a whole lot. The constant factors. The exact things we just ignored and threw away when we were factoring our nested loop. We threw away the constant overhead because n squared was assumed to get infinitely big. But if n is kept relatively small by physical memory limits, or just the practical size of a user's data, the overhead of a theoretically fast algorithm might actually make it run slower than a theoretically slow algorithm. That is wild. And I love the example our sources provide for this.

19:32It's about an algorithm called TimSort. Oh, TimSort is fascinating. Yeah. Now, we talked about insertion sort earlier with the playing cards. We proved it was O of n squared. It grows quadratically. It's generally considered a bad slow algorithm for large data. Correct. And then there are highly efficient algorithms, like mergeSort, which operated that much flatter O of n log n curve. Under big O notation, mergeSort wins every single time as the data scales up. But TimSort is what's known as a hybrid algorithm. It's actually the default sorting algorithm used in incredibly popular programming languages like Python. Which is everywhere. Right. TimSort uses the highly efficient mergeSort for the big chunks of data. But when the data chunks get small enough, TimSort actually deliberately switches back to the theoretically inefficient insertion sort. It actively chooses to use the O of n squared algorithm. Yes. And why would it do that? Because the highly efficient mergeSort works by constantly dividing lists and allocating new memory spaces to merge them back together.

20:33That takes a lot of time behind the scenes. Right. That requires a lot of complex overhead. PythonSort is incredibly simple. It just swaps the playing cards in place. For small amounts of data, the simple theoretically terrible algorithm just runs faster in reality, because it skips all the heavy setup time. It's a perfect compromise between pure mathematical theory and practical engineering. For small data sets, an asymptotically inefficient algorithm with low overhead is absolutely more efficient in practice. What a journey. I mean, we started off proving how deceptive empirical speed tests can be with our state of the art computer losing to the clunker because of a linear versus logarithmic search. Yeah. That showed us why we needed the theoretical landscape of big O notation and cost models to truly understand growth curves. And we learned how analysts mathematically evaluate code by counting discrete steps and looking for the dominant, highest order term that swallows the rest. But then we brought it all back down to Earth, realizing that in a finite world with memory

21:34limits, practical compromises like Tim Sort are totally necessary. The constant factors still have a voice. The stakes for getting this right are incredibly high too. The source material emphasizes this explicitly. The accidental or unintentional use of an inefficient algorithm can dramatically impact system performance. Absolutely. In time-sensitive applications, an algorithm taking too long can render its results entirely useless. If a weather prediction algorithm takes 48 hours to predict tomorrow's weather. We've missed the window. You missed it. The data is worthless. Or, you know, it devours an uneconomical amount of computing power. Which brings up one final really provocative thought from our sources. We've spent almost this entire deep dive talking about efficiency in terms of time, runtime. Oh, right. How fast it goes. But this mathematical methodology applies equally to other resources, though. Exactly. It applies to space, memory consumption. The text gives a chilling example of a file management algorithm that attempts to reallocate memory based on file size.

22:36If designed poorly, the memory consumption exhibits an exponential growth rate order 0 of 2 to the n. Oh, man. 0 of 2 to the n is a terrifying curve. It is a hyper-rapid, utterly unmanageable growth rate. Think about how a badly defined algorithm like that might actually work. Imagine a program scanning your hard drive. It finds a shortcut folder that accidentally points back to its own parent folder. The algorithm copies the parent folder into memory, then follows the shortcut, and copies the parent folder, again, inside itself. Right. It creates a recursive loop, doubling the amount of memory it's holding every single cycle. Two megabytes, 4, 8, 16, 32. Within moments, it would experiment to eventually duplicate data until it consumes all available memory and completely crashes the system. The space complexity becomes a fatal bottleneck long before time complexity even factors in. And this leaves you with something really fascinating to ponder. For decades, we've relied on hardware engineers to bail us out of bad memory hungry code, but you built faster processors and bigger hard drives.

23:39The whole idea behind Moore's law. We just kept doubling the transistors on the chips. Right. But physical computing hardware is currently hitting atomic limits. You can only make a transistor so small before quantum mechanics ruins the signal. It's just physics. Yeah. We literally cannot just build faster machines the way we used to, which means the ultimate bottleneck of the future is shifting away from the silicon microchip. It is shifting entirely onto the human mind's ability to design the perfect space and time efficient algorithm. If you want to win the race, you can't rely on upgrading the engine anymore. You have to know how to avoid the human sports car trap and build a better index for the library. You're listening to a podcast right now, driving, working out, walking the dog. If you're in a podcast, chances are you have something to say too. With rss.com, starting your own podcast is free and easy. Upload an episode and we distribute it to Apple podcasts, Spotify, Amazon Music and Moore. Track your listeners, see where they're from, and start earning from ads just like this. If you've been thinking about starting a podcast, this is your sign.

24:42Start your new podcast for free today at rss.com.