WEBVTT 00:00:00.000 --> 00:00:02.120 Imagine you were standing in the middle of a 00:00:02.120 --> 00:00:06.940 massive, completely disorganized library. Like, 00:00:08.039 --> 00:00:10.419 just books scattered absolutely everywhere on 00:00:10.419 --> 00:00:12.800 the floor. Exactly. Yeah. Millions of books, 00:00:12.939 --> 00:00:15.279 just everywhere. And you were looking for one 00:00:15.279 --> 00:00:18.000 specific title. Now, you could be the fastest 00:00:18.000 --> 00:00:19.859 runner on earth, right? Like a human sports car. 00:00:19.879 --> 00:00:22.879 Yeah. But if your strategy is literally just 00:00:22.879 --> 00:00:24.980 running down the aisles, looking at every single 00:00:24.980 --> 00:00:28.219 spine one by one. You're gonna lose. You are. 00:00:28.359 --> 00:00:31.460 A slow walker who just took a few minutes to 00:00:31.460 --> 00:00:33.380 check a master index is going to beat you to 00:00:33.380 --> 00:00:35.640 that book every single time. Because the physical 00:00:35.640 --> 00:00:37.740 speed of the runner doesn't actually matter if 00:00:37.740 --> 00:00:39.600 the fundamental method they're using to search 00:00:39.600 --> 00:00:42.960 is flawed. You just can't outrun a bad strategy. 00:00:43.060 --> 00:00:45.780 You really can't. And welcome to the Deep Dive. 00:00:45.859 --> 00:00:48.100 I'm your host. And that disorganized library 00:00:48.100 --> 00:00:50.380 is exactly the core of what we're unpacking today. 00:00:50.500 --> 00:00:52.840 I'm really excited for this one. I've spent years 00:00:52.840 --> 00:00:54.799 studying this exact topic, so it's going to be 00:00:54.799 --> 00:00:58.000 fun to dig in. Awesome. So we are pulling from 00:00:58.000 --> 00:01:01.079 a really comprehensive set of source material 00:01:01.079 --> 00:01:04.340 today, centered around this deeply detailed Wikipedia 00:01:04.340 --> 00:01:06.980 article on the analysis of algorithms. Right. 00:01:07.400 --> 00:01:09.659 And the mission of this deep dive for you listening 00:01:09.659 --> 00:01:13.239 is to basically figure out how computer scientists 00:01:13.239 --> 00:01:16.959 actually measure if an algorithm, which is the 00:01:16.959 --> 00:01:19.120 fundamental strategy your computer takes to solve 00:01:19.120 --> 00:01:22.290 a problem, if that algorithm is actually efficient. 00:01:22.450 --> 00:01:24.269 Because it's a lot more complicated than just 00:01:24.269 --> 00:01:26.290 hitting a stopwatch. It is, and we're going to 00:01:26.290 --> 00:01:29.290 see exactly why simply going out and buying a 00:01:29.290 --> 00:01:32.049 faster computer is often the absolute worst way 00:01:32.049 --> 00:01:35.530 to fix slow code. OK, let's unpack this. Efficiency 00:01:35.530 --> 00:01:37.230 in computer science, like you said, isn't just 00:01:37.230 --> 00:01:39.890 about stopwatches. No, not at all. It is usually 00:01:39.890 --> 00:01:41.969 about finding a mathematical function, right? 00:01:42.109 --> 00:01:44.750 Like a function that links the size of the input 00:01:44.750 --> 00:01:46.489 you're giving the computer to the number of steps 00:01:46.489 --> 00:01:49.250 it has to take or the amount of memory storage 00:01:49.250 --> 00:01:51.549 it requires. Yeah, because an algorithm is really 00:01:51.549 --> 00:01:54.329 just a recipe. OK, a recipe. Right. It's a specific 00:01:54.329 --> 00:01:56.730 set of instructions. And what analysts really 00:01:56.730 --> 00:01:59.189 need to know is what happens to those instructions 00:01:59.189 --> 00:02:01.590 when the problem gets bigger. Oh, I see. Like 00:02:01.590 --> 00:02:04.689 scaling up. Exactly. If we go from searching 00:02:04.689 --> 00:02:07.329 a small bookshelf to searching the Library of 00:02:07.329 --> 00:02:10.210 Congress, does the time it takes to follow that 00:02:10.210 --> 00:02:13.669 recipe grow by just a little bit? Or does it 00:02:13.669 --> 00:02:16.189 suddenly take, you know, an absolute eternity? 00:02:16.850 --> 00:02:19.289 Right, and let's start with a really striking 00:02:19.289 --> 00:02:21.509 visual from our source material that perfectly 00:02:21.509 --> 00:02:24.669 captures this difference in growth. Imagine you 00:02:24.669 --> 00:02:27.349 are looking for a specific name in a sorted list 00:02:27.349 --> 00:02:31.030 of, let's say, 33 items. Just 33, pretty small. 00:02:31.229 --> 00:02:33.169 Super small. Let's say you're looking for the 00:02:33.169 --> 00:02:36.129 name Morin, Arthur, if you use what's called 00:02:36.129 --> 00:02:38.629 a linear search. Which is the bad way. Right, 00:02:38.629 --> 00:02:40.750 the bad way. Which basically means starting at 00:02:40.750 --> 00:02:42.710 the top and checking every single name one by 00:02:42.710 --> 00:02:45.150 one. Completely ignoring the fact that the list 00:02:45.150 --> 00:02:47.009 is already in alphabetical order. Yeah, just 00:02:47.009 --> 00:02:50.270 brute forcing it. Exactly. It takes 28 check 00:02:50.270 --> 00:02:52.750 steps to finally find him in that list of 33. 00:02:53.370 --> 00:02:57.169 And, well, 28 steps for 33 items doesn't sound 00:02:57.169 --> 00:02:59.210 entirely catastrophic to a human. Like, you could 00:02:59.210 --> 00:03:01.560 do that in a minute. Right. But in the computing 00:03:01.560 --> 00:03:04.060 world, that's wildly inefficient. If you switch 00:03:04.060 --> 00:03:06.639 your strategy and use a binary search algorithm 00:03:06.639 --> 00:03:09.879 instead, it only takes five steps. Five steps 00:03:09.879 --> 00:03:13.439 instead of 28? Just five. Wow. Just to visualize 00:03:13.439 --> 00:03:16.159 how that works for you listening, binary search 00:03:16.159 --> 00:03:18.919 actually takes advantage of the list being in 00:03:18.919 --> 00:03:22.139 alphabetical order. It jumps right to the middle 00:03:22.139 --> 00:03:26.110 of the list and asks, Is Morin before or after 00:03:26.110 --> 00:03:27.870 this middle name? Exactly. And let's say it's 00:03:27.870 --> 00:03:30.189 before. It immediately throws away the entire 00:03:30.189 --> 00:03:32.050 back half of the list, then it goes to the middle 00:03:32.050 --> 00:03:34.289 of the remaining games, asks the same question, 00:03:34.610 --> 00:03:36.849 cuts the list in half again, and just repeats 00:03:36.849 --> 00:03:39.300 that. Yeah, the underlying mechanism there is 00:03:39.300 --> 00:03:41.639 having. Mathematically, theoretical analysis 00:03:41.639 --> 00:03:44.840 shows that for a list of size n, a binary search 00:03:44.840 --> 00:03:48.259 takes, at most, the base -2 logarithm of n steps. 00:03:48.360 --> 00:03:51.000 OK, base -2 logarithm. Just so we are totally 00:03:51.000 --> 00:03:53.159 clear here, that's basically just the mathematical 00:03:53.159 --> 00:03:55.360 term for that having process, right? That's right. 00:03:55.680 --> 00:03:57.819 Because you are repeatedly dividing the problem 00:03:57.819 --> 00:04:01.069 in two, The number of steps grows logarithmically 00:04:01.069 --> 00:04:04.069 rather than linearly. Got it. Whereas a linear 00:04:04.069 --> 00:04:06.909 search can take up to n steps. So if the list 00:04:06.909 --> 00:04:09.629 is a million items long, it might take a million 00:04:09.629 --> 00:04:13.830 checks. Which is brutal. And this stark difference 00:04:13.830 --> 00:04:17.269 in mechanisms brings us to this massive trap 00:04:17.269 --> 00:04:20.050 that, according to the source, even experienced 00:04:20.050 --> 00:04:22.550 programmers of massive tech companies still fall 00:04:22.550 --> 00:04:25.189 into. Oh, consciously. Lying on empirical testing. 00:04:25.589 --> 00:04:28.540 Yes. The empirical trap. So by empirical testing, 00:04:28.740 --> 00:04:31.060 the force basically means just running the code 00:04:31.060 --> 00:04:33.100 in the real world, like literally hitting go 00:04:33.100 --> 00:04:35.279 on a stopwatch to see how fast the program finishes. 00:04:35.680 --> 00:04:37.579 Right. And the problem with that is algorithms 00:04:37.579 --> 00:04:39.839 are actually platform independent. OK. What does 00:04:39.839 --> 00:04:42.500 that mean exactly? It means the pure logic of 00:04:42.500 --> 00:04:44.800 a binary search can run on any machine. It can 00:04:44.800 --> 00:04:47.639 be written in any programming language. Because 00:04:47.639 --> 00:04:50.139 of that, real world benchmark tests, where you 00:04:50.139 --> 00:04:53.100 just time the program, can be incredibly deceptive. 00:04:53.220 --> 00:04:55.610 Because the hardware gets in the way. Exactly. 00:04:56.029 --> 00:04:58.810 The hardware muddies the waters. The source provides 00:04:58.810 --> 00:05:00.870 a brilliant example to prove this, actually. 00:05:01.209 --> 00:05:03.470 Let's pit two computers against each other. OK, 00:05:03.470 --> 00:05:05.790 I love this example. We have computer A, which 00:05:05.790 --> 00:05:08.269 is this state of the art lightning fast machine, 00:05:08.930 --> 00:05:11.290 top of the line processor, incredible specs. 00:05:11.949 --> 00:05:15.670 But we are going to force it to run that slow 00:05:15.670 --> 00:05:18.870 linear search algorithm. So it's the human sports 00:05:18.870 --> 00:05:21.449 car checking every single book spine one by one. 00:05:21.670 --> 00:05:24.430 Yes, perfect analogy. And then we have computer 00:05:24.430 --> 00:05:27.610 B. Now, computer B is a much slower, older machine, 00:05:27.829 --> 00:05:30.829 just a total clunker. But computer B gets to 00:05:30.829 --> 00:05:33.550 run the highly efficient binary search algorithm. 00:05:34.290 --> 00:05:36.870 So if we do a benchmark test on a tiny list, 00:05:37.230 --> 00:05:40.790 say just 16 items, computer A finishes in 8 nanoseconds. 00:05:41.149 --> 00:05:44.209 Computer B takes 100 ,000 nanoseconds. OK. So 00:05:44.209 --> 00:05:45.990 if you're an engineer just looking at the results 00:05:45.990 --> 00:05:48.230 of that empirical test, you'd say, wow, computer 00:05:48.230 --> 00:05:50.810 A is absolutely crushing it. I mean, it's thousands 00:05:50.810 --> 00:05:53.730 of times faster. by more of computer A. You would 00:05:53.730 --> 00:05:55.449 jump to the conclusion that computer A is running 00:05:55.449 --> 00:05:57.649 a far superior system, yeah, and you would be 00:05:57.649 --> 00:05:59.930 dramatically wrong. Dramatically wrong. Because 00:05:59.930 --> 00:06:02.750 computer A is exhibiting a linear growth rate, 00:06:03.170 --> 00:06:05.629 its runtime is directly proportional to the input 00:06:05.629 --> 00:06:08.269 size. If you double the length of the list, you 00:06:08.269 --> 00:06:10.589 just double the time it takes. Right. Computer 00:06:10.589 --> 00:06:13.089 B, however, exhibits that logarithmic growth 00:06:13.089 --> 00:06:15.189 rate we talked about, because every single time 00:06:15.189 --> 00:06:17.949 it takes a step, it wipes out half of the remaining 00:06:17.949 --> 00:06:21.399 problem. Having it. Yeah, so if you exponentially 00:06:21.399 --> 00:06:24.519 quadruple the input size, its runtime only increases 00:06:24.519 --> 00:06:27.300 by a tiny constant amount. Okay, here's where 00:06:27.300 --> 00:06:29.720 it gets really interesting. If we keep ramping 00:06:29.720 --> 00:06:32.519 up the size of that list, that massive gap starts 00:06:32.519 --> 00:06:35.139 to close, right? By the time we feed both computers 00:06:35.139 --> 00:06:37.920 a list of 1 million items, they actually tie. 00:06:38.089 --> 00:06:40.829 They do. They both take exactly 500 ,000 nanoseconds. 00:06:40.970 --> 00:06:43.529 Yeah. That tie at 1 million items is the tipping 00:06:43.529 --> 00:06:45.290 point. And the list obviously doesn't have to 00:06:45.290 --> 00:06:47.670 stop at a million. Let's say we scale up the 00:06:47.670 --> 00:06:51.810 input size to about 63 trillion items. OK, 63 00:06:51.810 --> 00:06:55.569 trillion. That's 63 .772 times 10 to the 12th 00:06:55.569 --> 00:06:57.949 power. Computer B, our slow clunker with the 00:06:57.949 --> 00:06:59.970 smart algorithm, finishes searching that massive 00:06:59.970 --> 00:07:04.389 list in just 1 .375 milliseconds. OK, wait. So 00:07:04.389 --> 00:07:07.420 Computer B takes just over 1 millisecond. What 00:07:07.420 --> 00:07:10.009 about computer A? The state -of -the -art machine 00:07:10.009 --> 00:07:12.709 checking, one by one. Computer A will take exactly 00:07:12.709 --> 00:07:15.230 one year to finish. A whole year. Seriously, 00:07:15.370 --> 00:07:17.230 the math actually works out to a full year. It 00:07:17.230 --> 00:07:19.170 works out perfectly to a year, because to check 00:07:19.170 --> 00:07:22.569 63 trillion items linearly at the speed it was 00:07:22.569 --> 00:07:25.290 going, the time just scales directly. That is 00:07:25.290 --> 00:07:28.029 insane. Right. It proves, without a shadow of 00:07:28.029 --> 00:07:30.110 a doubt, that algorithm design completely trumps 00:07:30.110 --> 00:07:32.310 hardware speed when you are operating at scale. 00:07:32.930 --> 00:07:35.649 A faster processor just cannot save you from 00:07:35.649 --> 00:07:38.439 a linear growth rate. Okay, so if empirical Testing 00:07:38.439 --> 00:07:41.240 is a trap, right? And if you can't trust a stopwatch 00:07:41.240 --> 00:07:44.300 because hardware muddies the waters, how on earth 00:07:44.300 --> 00:07:46.519 did computer scientists actually figure out a 00:07:46.519 --> 00:07:48.959 way to prove one algorithm was better than another? 00:07:49.399 --> 00:07:51.259 Well, they had to step away from physical testing 00:07:51.259 --> 00:07:54.259 completely and use pure mathematics, specifically 00:07:54.259 --> 00:07:57.439 what the source text calls asymptotic estimates. 00:07:57.860 --> 00:08:00.040 Asymptotic estimates? Yeah, they allow us to 00:08:00.040 --> 00:08:02.160 estimate the complexity of an algorithm for an 00:08:02.160 --> 00:08:05.319 arbitrarily large input. Basically, we ask, what 00:08:05.319 --> 00:08:07.180 happens to the math when the data approaches 00:08:07.180 --> 00:08:10.560 infinity? Ah, okay. When things get infinitely 00:08:10.560 --> 00:08:13.639 big. Exactly. To do this, computer scientists 00:08:13.639 --> 00:08:16.740 use notations like big omega, big theta, and 00:08:16.740 --> 00:08:20.139 the most famous one, big O notation. The term 00:08:20.139 --> 00:08:23.060 analysis of algorithms and much of this methodology 00:08:23.060 --> 00:08:25.180 was actually coined by the legendary computer 00:08:25.180 --> 00:08:27.680 scientist Donald Newth. Right, Donald Newth. 00:08:27.779 --> 00:08:30.819 Okay, so big O notation. You know, the way I 00:08:30.819 --> 00:08:32.500 finally wrapped my head around this was thinking 00:08:32.500 --> 00:08:35.080 about describing the absolute worst -case scenario 00:08:35.080 --> 00:08:37.620 for a road trip. Oh, I like that. Yeah, like, 00:08:37.799 --> 00:08:40.059 if you're going to visit a friend and you tell 00:08:40.059 --> 00:08:42.679 them, look, at worst it will take me three hours 00:08:42.679 --> 00:08:45.200 to drive there, you are placing an upper limit 00:08:45.200 --> 00:08:47.679 on the time. Right, an upper bound. Exactly. 00:08:48.039 --> 00:08:50.679 Even if there's traffic or a detour, it won't 00:08:50.679 --> 00:08:53.580 take more than three hours. In mathematical terms, 00:08:53.740 --> 00:08:56.419 Big O says that beyond a certain point, the runtime 00:08:56.419 --> 00:08:59.179 of an algorithm will never be larger than a constant, 00:08:59.539 --> 00:09:03.139 let's call it C, multiplied by a specific mathematical 00:09:03.139 --> 00:09:06.470 function of the input size, f of n. Right. It 00:09:06.470 --> 00:09:08.289 just places a hard ceiling on how bad things 00:09:08.289 --> 00:09:10.970 can get as the data grows. That road trip analogy 00:09:10.970 --> 00:09:13.549 perfectly captures the spirit of the upper bound. 00:09:14.210 --> 00:09:17.889 For example, let's look at sorting data. If you 00:09:17.889 --> 00:09:20.669 are sorting a list of numbers using an algorithm 00:09:20.669 --> 00:09:24.009 called insertion sort, its worst case runtime 00:09:24.009 --> 00:09:26.990 grows quadratically. Quadratically. Yeah. So 00:09:26.990 --> 00:09:30.009 we say it is of order O of N squared. Let me 00:09:30.009 --> 00:09:32.009 make sure I'm picturing insertion sort correctly. 00:09:32.370 --> 00:09:35.080 That's kind of like organizing a hand of playing 00:09:35.080 --> 00:09:37.220 cards, right? Yes, exactly. They can pick up 00:09:37.220 --> 00:09:39.340 a new card and you have to compare it to every 00:09:39.340 --> 00:09:41.759 single card already in your hand to find exactly 00:09:41.759 --> 00:09:43.700 where it goes. That's the exact mechanism. If 00:09:43.700 --> 00:09:46.399 you have N cards, you are doing roughly N comparisons 00:09:46.399 --> 00:09:48.860 for every single one of those N cards. Hence, 00:09:49.120 --> 00:09:52.220 N times N or N squared. Right. If you double 00:09:52.220 --> 00:09:55.019 the amount of data, the time it takes quadruples. 00:09:55.100 --> 00:09:57.360 If you triple the data, the time increases by 00:09:57.360 --> 00:10:00.519 nine times. Which, as we saw with the linear 00:10:00.519 --> 00:10:02.799 search versus binary search, is a growth rate 00:10:02.799 --> 00:10:04.850 you really want to pay attention to. to because 00:10:04.850 --> 00:10:07.090 an O of n squared algorithm is going to hit a 00:10:07.090 --> 00:10:10.649 wall very fast. It will. It really will. Now, 00:10:10.690 --> 00:10:13.570 while big O is incredibly useful for expressing 00:10:13.570 --> 00:10:16.610 that worst case road trip scenario, our sources 00:10:16.610 --> 00:10:19.570 make sure to note it can express average cases 00:10:19.570 --> 00:10:21.850 too. Oh, interesting. So it's not just the worst 00:10:21.850 --> 00:10:24.309 case. Right. Take another sorting algorithm. 00:10:24.450 --> 00:10:27.409 Quick sort. Its absolute worst case scenario 00:10:27.409 --> 00:10:31.250 is also O of n squared. But because of how it 00:10:31.250 --> 00:10:34.610 divides data, On average, its runtime is actually 00:10:34.610 --> 00:10:37.210 O of n log n. Which is better. Which is a much, 00:10:37.230 --> 00:10:40.350 much flatter, faster curve. OK, so we have this 00:10:40.350 --> 00:10:43.409 theoretical language to describe growth. We know 00:10:43.409 --> 00:10:45.929 O of n squared is generally worse than O of n 00:10:45.929 --> 00:10:49.009 log n at scale, because we are looking at the 00:10:49.009 --> 00:10:50.990 shape of the mathematical curve. This raises 00:10:50.990 --> 00:10:53.629 an important question, though. How can we mathematically 00:10:53.629 --> 00:10:56.129 tally up the steps an algorithm takes to build 00:10:56.129 --> 00:10:58.350 these curves if we haven't even defined what 00:10:58.350 --> 00:11:01.269 a single step actually is in the math? Ah, right. 00:11:01.330 --> 00:11:03.080 Good point. point, because if we are throwing 00:11:03.080 --> 00:11:05.159 away the stopwatch and ignoring the computer's 00:11:05.159 --> 00:11:07.399 actual hardware, what are we even counting? Exactly. 00:11:07.620 --> 00:11:09.759 Like a step for a massive supercomputer is very 00:11:09.759 --> 00:11:13.340 different from a step for a smart fridge. Completely 00:11:13.340 --> 00:11:16.620 different. So for this theoretical analysis to 00:11:16.620 --> 00:11:19.700 correspond usefully to actual runtime, we have 00:11:19.700 --> 00:11:21.659 to guarantee that the time required to perform 00:11:21.659 --> 00:11:25.409 a step is bounded by a constant. To standardize 00:11:25.409 --> 00:11:28.049 this, computer scientists generally use two different 00:11:28.049 --> 00:11:30.970 cost models. OK, cost models. The first is the 00:11:30.970 --> 00:11:33.509 uniform cost model, sometimes called the unit 00:11:33.509 --> 00:11:36.429 cost model. This model assigns a constant cost 00:11:36.429 --> 00:11:40.110 of 1 to every single machine operation, regardless 00:11:40.110 --> 00:11:42.190 of the size of the numbers involved. Wait, hold 00:11:42.190 --> 00:11:43.730 on a second. Let me push back on that. Sure. 00:11:43.970 --> 00:11:46.409 So under this uniform cost model, you're saying 00:11:46.409 --> 00:11:49.330 adding 1 plus 1 takes the exact same amount of 00:11:49.330 --> 00:11:53.240 time as adding two numbers that each have a billion 00:11:53.240 --> 00:11:55.399 digits. Under that model, yes. But that seems 00:11:55.399 --> 00:11:57.399 physically impossible. I mean, a computer actually 00:11:57.399 --> 00:11:59.379 has to process all those extra digits. That feels 00:11:59.379 --> 00:12:02.220 completely unrealistic for massive computations. 00:12:02.399 --> 00:12:05.000 You've hit on the exact flaw of the uniform cost 00:12:05.000 --> 00:12:07.159 model. It is physically impossible to process 00:12:07.159 --> 00:12:09.279 a billion digits in the same time it takes to 00:12:09.279 --> 00:12:12.100 process one. The physical logic gates in a computer 00:12:12.100 --> 00:12:15.559 require more time to process more bits of information. 00:12:16.240 --> 00:12:18.879 This assumption of constant time is a simplification. 00:12:18.879 --> 00:12:20.639 And you're right, it's not always warranted. 00:12:20.429 --> 00:12:23.490 which is exactly why the second model exists, 00:12:24.250 --> 00:12:27.250 the logarithmic cost model. Okay, that sounds 00:12:27.250 --> 00:12:30.129 like it counts for the size. It does. The logarithmic 00:12:30.129 --> 00:12:33.129 cost model assigns a cost to every machine operation 00:12:33.129 --> 00:12:35.470 that is proportional to the number of bits involved. 00:12:35.649 --> 00:12:37.750 Oh, bits, so... Yeah, so adding those billion 00:12:37.750 --> 00:12:40.370 -digit numbers would cost significantly more 00:12:40.370 --> 00:12:42.850 theoretical steps than adding 1 plus 1. That 00:12:42.850 --> 00:12:45.649 makes perfect sense. So if the logarithmic model 00:12:45.649 --> 00:12:48.029 is more accurate to reality, why wouldn't they 00:12:48.029 --> 00:12:49.950 just use it all the time? Well, because it is 00:12:49.950 --> 00:12:52.549 incredibly cumbersome to calculate. Too much 00:12:52.549 --> 00:12:55.490 math. Way too much math. In daily programming, 00:12:55.789 --> 00:12:58.370 The numbers we deal with usually fit comfortably 00:12:58.370 --> 00:13:02.149 within standard fixed memory sizes, like a 32 00:13:02.149 --> 00:13:05.669 -bit integer or a 64 -bit integer. Because the 00:13:05.669 --> 00:13:07.830 physical size of the numbers is capped by the 00:13:07.830 --> 00:13:10.330 system, pretending they all take the same constant 00:13:10.330 --> 00:13:13.090 time doesn't actually skew the mathematical results 00:13:13.090 --> 00:13:15.440 enough to matter. So it's just practical. Yeah, 00:13:15.580 --> 00:13:18.299 the uniform model is good enough for standard 00:13:18.299 --> 00:13:20.860 software. The logarithmic model is really only 00:13:20.860 --> 00:13:23.860 employed when absolutely necessary. So what's 00:13:23.860 --> 00:13:25.779 a scenario where it's absolutely necessary? Like 00:13:25.779 --> 00:13:28.980 when do you have to use it? The analysis of arbitrary 00:13:28.980 --> 00:13:32.620 precision arithmetic. A prime example is cryptography. 00:13:32.879 --> 00:13:36.320 Oh, like security stuff. Exactly. When you are 00:13:36.320 --> 00:13:39.419 encrypting secure data like banking information 00:13:39.419 --> 00:13:42.139 over the internet, you aren't working with normal 00:13:42.139 --> 00:13:44.899 10 -digit numbers. You are working with astronomically 00:13:44.899 --> 00:13:47.860 large numbers with hundreds or thousands of digits 00:13:47.860 --> 00:13:50.379 just to make it impossible for hackers to guess 00:13:50.379 --> 00:13:52.679 them. Wow. And the computer has to break those 00:13:52.679 --> 00:13:54.799 massive numbers into smaller chunks just to add 00:13:54.799 --> 00:13:57.559 or multiply them. In those cases, the size of 00:13:57.559 --> 00:13:59.539 the number dramatically impacts the time it takes 00:13:59.539 --> 00:14:02.340 to compute. So using the logarithmic cost model, 00:14:02.220 --> 00:14:04.960 is essential to get an accurate O notation there. 00:14:05.100 --> 00:14:07.759 Got it. So for everyday analysis, we just stick 00:14:07.759 --> 00:14:11.000 to the uniform cost model, assuming each basic 00:14:11.000 --> 00:14:13.720 step takes one unit of time. Right. So assuming 00:14:13.720 --> 00:14:15.980 that uniform model, how do we analysts actually 00:14:15.980 --> 00:14:18.100 peek under the hood and tally up the steps in 00:14:18.100 --> 00:14:21.350 a piece of code? They evaluate the runtime complexity 00:14:21.350 --> 00:14:23.610 by looking at the structure of the algorithm 00:14:23.610 --> 00:14:26.730 itself. Usually, analysts will break down a piece 00:14:26.730 --> 00:14:28.769 of pseudocode. Pseudocode. Yeah, which is like 00:14:28.769 --> 00:14:31.009 a simplified, human -readable version of the 00:14:31.009 --> 00:14:34.970 code. And they assign discrete time units to 00:14:34.970 --> 00:14:37.009 the different instructions. They might say step 00:14:37.009 --> 00:14:40.070 one takes time t1, step two takes t2, and so 00:14:40.070 --> 00:14:41.850 on. OK, that seems simple enough. You just read 00:14:41.850 --> 00:14:44.649 down the list and add up all the t's. It is simple 00:14:44.649 --> 00:14:48.240 until the code loops. Especially nested loops 00:14:48.240 --> 00:14:50.299 when you have a loop running inside another loop. 00:14:50.799 --> 00:14:53.039 That's where the math gets tricky and where the 00:14:53.039 --> 00:14:56.200 real runtime cost of an algorithm usually hides. 00:14:56.419 --> 00:14:58.360 Okay, let me make sure I'm picturing this nested 00:14:58.360 --> 00:15:01.399 loop math correctly. Is it kind of like a handshake 00:15:01.399 --> 00:15:04.379 line at a party? Okay, let's hear it. Let's say 00:15:04.379 --> 00:15:06.960 the party is our outer loop. The total number 00:15:06.960 --> 00:15:09.639 of people at the party is n. Right. The first 00:15:09.639 --> 00:15:11.710 person walks into the room. and there's only 00:15:11.710 --> 00:15:14.669 one person to shake hands with. So one handshake. 00:15:15.149 --> 00:15:17.710 That's the inner loop running once. Then the 00:15:17.710 --> 00:15:19.970 second person walks in, and now there are two 00:15:19.970 --> 00:15:21.470 people in the room, so they have to shake two 00:15:21.470 --> 00:15:24.429 hands. The third person shakes three hands. And 00:15:24.429 --> 00:15:26.629 this just keeps escalating until the last person, 00:15:26.629 --> 00:15:29.029 person N, walks in and has to shake in hands. 00:15:29.250 --> 00:15:31.789 That is a brilliant way to visualize it because 00:15:31.789 --> 00:15:34.909 the inner loops iterations grow exactly like 00:15:34.909 --> 00:15:37.929 that sequence, an arithmetic progression. It's 00:15:37.929 --> 00:15:41.039 one plus two plus three. all the way up to n. 00:15:41.240 --> 00:15:43.500 So if we want to know the total time that inner 00:15:43.500 --> 00:15:45.899 loop takes, like the total number of handshakes 00:15:45.899 --> 00:15:48.820 at the party, we have to add all those escalating 00:15:48.820 --> 00:15:50.980 numbers together. And luckily, mathematics gives 00:15:50.980 --> 00:15:53.360 us a shortcut formula for adding up an arithmetic 00:15:53.360 --> 00:15:56.360 progression. The sum of that entire sequence 00:15:56.360 --> 00:15:58.840 factors out to one half times the quantity of 00:15:58.840 --> 00:16:01.639 n squared plus n. OK, so in formula terms, that's 00:16:01.639 --> 00:16:04.059 one half times n squared plus n. Right. And when 00:16:04.059 --> 00:16:06.639 we map out the entire algorithm, adding the constant 00:16:06.639 --> 00:16:09.740 times for t1, t2, the test to see if the outer 00:16:09.740 --> 00:16:12.159 loop should keep running and this newly factored 00:16:12.159 --> 00:16:15.000 inner loop, we end up with a very long messy 00:16:15.000 --> 00:16:17.899 polynomial equation. Sounds messy. But here is 00:16:17.899 --> 00:16:20.419 the crucial takeaway for anyone evaluating complexity. 00:16:21.200 --> 00:16:23.919 The highest order term dominates the growth rate. 00:16:24.220 --> 00:16:27.620 The highest order term, meaning like the part 00:16:27.620 --> 00:16:29.940 of the equation with the biggest exponent. Yes. 00:16:30.220 --> 00:16:32.799 In our handshake equation, the highest order 00:16:32.799 --> 00:16:35.960 term is the n squared. As n, the size of our 00:16:35.960 --> 00:16:38.220 data, gets larger and larger, that n squared 00:16:38.220 --> 00:16:41.620 part of the math grows so massively that it entirely 00:16:41.620 --> 00:16:43.919 swallows all the smaller terms and the constant 00:16:43.919 --> 00:16:47.100 factors. It just dwarfs them. Exactly. The linear 00:16:47.100 --> 00:16:50.120 n terms, the 1 halves, the t ones, they all become 00:16:50.120 --> 00:16:53.039 statistically insignificant. Because if n is 00:16:53.039 --> 00:16:55.559 a million, a million squared is a trillion. Yep. 00:16:56.220 --> 00:16:58.919 and adding a few extra million on top of a trillion 00:16:58.919 --> 00:17:01.299 from the other parts of the equation doesn't 00:17:01.299 --> 00:17:03.320 really change the trajectory of the curve. Not 00:17:03.320 --> 00:17:05.680 at all. We can mathematically prove that the 00:17:05.680 --> 00:17:07.839 function's growth is bounded by that n squared. 00:17:08.420 --> 00:17:10.740 Therefore, the algorithm's runtime order is officially 00:17:10.740 --> 00:17:13.940 declared to be O of n squared. We've proven it, 00:17:14.039 --> 00:17:16.380 theoretically, mapping the code directly to a 00:17:16.380 --> 00:17:18.640 curve without ever needing a physical stopwatch. 00:17:19.039 --> 00:17:20.779 So what does this all mean? We've built this 00:17:20.779 --> 00:17:22.779 entire theoretical framework on the assumption 00:17:22.779 --> 00:17:25.750 that data approaches infinity. That's why big 00:17:25.750 --> 00:17:28.789 O works. Because at infinity, n squared gets 00:17:28.789 --> 00:17:31.190 so unimaginably huge, it just swallows everything 00:17:31.190 --> 00:17:34.869 else. Yes, that's the theory. But we don't live 00:17:34.869 --> 00:17:37.269 in an infinite world. We certainly do not. And 00:17:37.269 --> 00:17:41.190 that introduces a massive real -world plot twist 00:17:41.190 --> 00:17:43.990 in the analysis of algorithms. Plot twist. Yeah. 00:17:44.289 --> 00:17:47.630 Big O focuses on asymptotic performance, what 00:17:47.630 --> 00:17:51.089 happens as things get unimaginably large. But 00:17:51.089 --> 00:17:53.509 real -world data is practically always limited 00:17:53.509 --> 00:17:56.150 in size. because it's limited by the physical 00:17:56.150 --> 00:17:58.190 constraints of addressable memory, right? Yeah. 00:17:58.190 --> 00:17:59.950 Our computers only have so much RAM to hold data 00:17:59.950 --> 00:18:03.230 in the first place. Precisely. On a 32 -bit machine, 00:18:03.529 --> 00:18:06.230 your limit is usually 4 gigabytes, which is the 00:18:06.230 --> 00:18:08.309 strict technical term for how computers measure 00:18:08.309 --> 00:18:10.990 a gigabyte based on powers of 2. Right. On a 00:18:10.990 --> 00:18:13.589 modern 64 -bit machine, the addressable limit 00:18:13.589 --> 00:18:17.210 is 16 XB bytes. Now, 16 XB bytes is a staggering 00:18:17.210 --> 00:18:19.670 amount of memory, but it is deeply physically 00:18:19.670 --> 00:18:22.019 finite. Right. It's not infinity. And because 00:18:22.019 --> 00:18:25.640 our data cannot actually reach infinity, an incredible 00:18:25.640 --> 00:18:29.019 thing happens to the math. The constant factors 00:18:29.019 --> 00:18:31.680 suddenly matter a whole lot. The constant factors. 00:18:31.940 --> 00:18:34.839 The exact things we just ignored and threw away 00:18:34.839 --> 00:18:36.819 when we were factoring our nested loop. We threw 00:18:36.819 --> 00:18:38.900 away the constant overhead because n squared 00:18:38.900 --> 00:18:41.900 was assumed to get infinitely big. But if n is 00:18:41.900 --> 00:18:44.720 kept relatively small by physical memory limits 00:18:44.720 --> 00:18:47.359 or just the practical size of a user's data, 00:18:47.900 --> 00:18:50.940 the overhead of a theoretically fast algorithm 00:18:50.940 --> 00:18:53.640 might actually make it run slower than a theoretically 00:18:53.640 --> 00:18:56.740 slow algorithm. That is wild. And I love the 00:18:56.740 --> 00:18:58.559 example our sources provide for this. It's about 00:18:58.559 --> 00:19:01.319 an algorithm called TimSort. Oh, TimSort is f 00:19:01.319 --> 00:19:03.450 - Fascinating. Yeah. Now we talked about insertion 00:19:03.450 --> 00:19:05.650 sort earlier with the playing cards. We proved 00:19:05.650 --> 00:19:07.869 it was O of n squared. It grows quadratically. 00:19:08.069 --> 00:19:10.210 It's generally considered a bad, slow algorithm 00:19:10.210 --> 00:19:12.710 for large data. Correct. And then there are highly 00:19:12.710 --> 00:19:14.970 efficient algorithms, like merge sort, which 00:19:14.970 --> 00:19:17.710 operated that much flatter O of n log n curve. 00:19:18.109 --> 00:19:21.630 Under big O notation, merge sort wins every single 00:19:21.630 --> 00:19:24.769 time as the data scales up. But TimSort is what's 00:19:24.769 --> 00:19:27.930 known as a hybrid algorithm. It's actually the 00:19:27.930 --> 00:19:30.390 default sorting algorithm used in incredibly 00:19:30.390 --> 00:19:32.690 popular programming languages like Python. Which 00:19:32.690 --> 00:19:35.890 is everywhere. Right. TimSort uses the highly 00:19:35.890 --> 00:19:38.170 efficient merge sort for the big chunks of data. 00:19:38.670 --> 00:19:41.109 But when the data chunks get small enough, TimSort 00:19:41.109 --> 00:19:43.450 actually deliberately switches back to the theoretically 00:19:43.450 --> 00:19:46.190 inefficient insertion sort. It actively chooses 00:19:46.190 --> 00:19:49.690 to use the O of N squared algorithm. Yes. And 00:19:49.690 --> 00:19:52.230 why would it do that? Because the highly efficient 00:19:52.230 --> 00:19:55.309 merge sort works by constantly dividing lists 00:19:55.309 --> 00:19:58.369 and allocating new memory spaces to merge them 00:19:58.369 --> 00:20:00.369 back together. That takes a lot of time behind 00:20:00.369 --> 00:20:02.789 the scenes. Right. That requires a lot of complex 00:20:02.789 --> 00:20:05.309 overhead. Insertion sort is incredibly simple. 00:20:05.430 --> 00:20:08.029 It just swaps the playing cards in place. For 00:20:08.029 --> 00:20:10.210 small amounts of data, the simple theoretically 00:20:10.210 --> 00:20:12.730 terrible algorithm just runs faster in reality 00:20:12.730 --> 00:20:15.309 because it skips all the heavy setup time. It's 00:20:15.309 --> 00:20:18.049 a perfect compromise between pure mathematical 00:20:18.049 --> 00:20:21.509 theory and practical engineering. For small datasets, 00:20:21.809 --> 00:20:23.990 an asymptotically inefficient algorithm with 00:20:23.990 --> 00:20:26.630 low overhead is absolutely more efficient in 00:20:26.630 --> 00:20:29.410 practice. What a journey! I mean, we started 00:20:29.410 --> 00:20:32.029 off proving how deceptive empirical speed tests 00:20:32.029 --> 00:20:34.470 can be with our state -of -the -art computer 00:20:34.470 --> 00:20:37.069 losing to the clunker because of a linear versus 00:20:37.069 --> 00:20:40.349 logarithmic search. That showed us why we needed 00:20:40.349 --> 00:20:43.369 the theoretical landscape of big O notation and 00:20:43.369 --> 00:20:46.710 cost models to truly understand growth curves. 00:20:46.910 --> 00:20:49.849 And we learned how analysts mathematically evaluate 00:20:49.849 --> 00:20:53.230 code by counting discrete steps and looking for 00:20:53.230 --> 00:20:55.650 the dominant highest order term that swallows 00:20:55.650 --> 00:20:57.670 the rest. But then we brought it all back down 00:20:57.670 --> 00:21:00.069 to earth, realizing that in a finite world with 00:21:00.069 --> 00:21:03.130 memory limits, practical compromises like TimSort 00:21:03.130 --> 00:21:06.670 are totally necessary. The constant factors still 00:21:06.670 --> 00:21:08.900 have a voice. The stakes for getting this right 00:21:08.900 --> 00:21:11.359 are incredibly high, too. The source material 00:21:11.359 --> 00:21:14.640 emphasizes this explicitly. The accidental or 00:21:14.640 --> 00:21:16.700 unintentional use of an inefficient algorithm 00:21:16.700 --> 00:21:19.640 can dramatically impact system performance. Absolutely. 00:21:19.799 --> 00:21:21.920 In time -sensitive applications, an algorithm 00:21:21.920 --> 00:21:24.579 taking too long can render its results entirely 00:21:24.579 --> 00:21:27.220 useless. If a weather prediction algorithm takes 00:21:27.220 --> 00:21:29.660 48 hours to predict tomorrow's weather... You've 00:21:29.660 --> 00:21:31.799 missed the window. You missed it. The data is 00:21:31.799 --> 00:21:34.920 worthless. Or, you know, it devours an uneconomical 00:21:34.920 --> 00:21:37.440 amount of computing power. which brings up one 00:21:37.440 --> 00:21:39.799 final really provocative thought from our sources. 00:21:40.599 --> 00:21:42.779 We've spent almost this entire deep dive talking 00:21:42.779 --> 00:21:45.920 about efficiency in terms of time, runtime. Right, 00:21:46.039 --> 00:21:49.259 how fast it goes. But this mathematical methodology 00:21:49.259 --> 00:21:51.680 applies equally to other resources though. Exactly, 00:21:51.799 --> 00:21:55.180 it applies to space. Memory consumption. The 00:21:55.180 --> 00:21:57.420 text gives a chilling example of a file management 00:21:57.420 --> 00:22:00.180 algorithm that attempts to reallocate memory 00:22:00.180 --> 00:22:03.759 based on file size. If designed poorly, The memory 00:22:03.759 --> 00:22:05.839 consumption exhibits an exponential growth rate 00:22:05.839 --> 00:22:08.920 order O of 2 to the N. Oh man, O of 2 to the 00:22:08.920 --> 00:22:11.400 N is a terrifying curve. It is a hyper rapid, 00:22:11.640 --> 00:22:14.259 utterly unmanageable growth rate. Think about 00:22:14.259 --> 00:22:16.559 how a badly defined algorithm like that might 00:22:16.559 --> 00:22:19.059 actually work. Imagine a program scanning your 00:22:19.059 --> 00:22:22.380 hard drive. It finds a shortcut folder that accidentally 00:22:22.380 --> 00:22:25.220 points back to its own parent folder. The algorithm 00:22:25.220 --> 00:22:27.680 copies the parent folder into memory, then follows 00:22:27.680 --> 00:22:29.980 the shortcut and copies the parent folder again 00:22:29.980 --> 00:22:32.720 inside itself. Right, it creates a recursive 00:22:32.720 --> 00:22:35.009 loop. doubling the amount of memory it's holding 00:22:35.009 --> 00:22:38.349 every single cycle. Two megabytes, four, eight, 00:22:38.609 --> 00:22:42.710 16, 32. Within moments, it would exponentially 00:22:42.710 --> 00:22:45.670 duplicate data until it consumes all available 00:22:45.670 --> 00:22:48.309 memory and completely crashes the system. The 00:22:48.309 --> 00:22:51.069 space complexity becomes a fatal bottleneck long 00:22:51.069 --> 00:22:54.269 before time complexity even factors in. And this 00:22:54.269 --> 00:22:55.690 leaves you with something really fascinating 00:22:55.690 --> 00:22:58.839 to ponder. For decades, we've relied on hardware 00:22:58.839 --> 00:23:01.299 engineers to bail us out of bad memory -hungry 00:23:01.299 --> 00:23:04.500 code, but building faster processors and bigger 00:23:04.500 --> 00:23:06.859 hard drives. The whole idea behind Moore's Law. 00:23:07.119 --> 00:23:08.960 We just kept doubling the transistors on the 00:23:08.960 --> 00:23:11.079 chips. Right. But physical computing hardware 00:23:11.079 --> 00:23:13.799 is currently hitting atomic limits. You can only 00:23:13.799 --> 00:23:16.099 make a transistor so small before quantum mechanics 00:23:16.099 --> 00:23:19.200 ruins the signal. It's just physics. Yeah. We 00:23:19.200 --> 00:23:21.559 literally cannot just build faster machines the 00:23:21.559 --> 00:23:24.380 way we used to. Which means the ultimate bottleneck 00:23:24.380 --> 00:23:26.460 of the future is shifting away from the silicon 00:23:26.460 --> 00:23:29.299 microchip. It is shifting entirely onto the human 00:23:29.299 --> 00:23:31.920 mind's ability to design the perfect space and 00:23:31.920 --> 00:23:33.940 time efficient algorithm. If you want to win 00:23:33.940 --> 00:23:36.000 the race, you can't rely on upgrading the engine 00:23:36.000 --> 00:23:38.539 anymore. You have to know how to avoid the human 00:23:38.539 --> 00:23:41.519 sports car trap and build a better index for 00:23:41.519 --> 00:23:42.019 the library.