So, the example that I've given involving the experiments, development of mathematical models relatively detailed and it doesn't seem like something that you might want to do for every program that you write. But there is something that you can do that's very simple and that you should do for every program that's going to consume considerable amount of resources, and that's what we're going to talk about next, it's called the doubling method for analyzing performance. So, a key question that definitely comes to mind is, is it really true that the running time of my program is going to satisfy a power law? It's going to be proportional to a constant times N to another constant? The answer is absolutely there's a very good chance of that. There's some that don't, but there's a really good chance that yours will with the caveat that there might be a factor of log N to some small power. So, how can I say that so confidently? Well, for one thing, is we've studied lots and lots of specific algorithms, and we've observed this for many algorithms with rigorous mathematical models backed up by performance studies, that's what Canu's work's all about, and that's what you can learn about in algorithms. The other thing is that, as I mentioned, we use simple constructs to build programs, and I'll give some more examples of that. Also, the data that we process often is pretty simply structured or at least has characteristics of simply structured data. In fact, deeper mathematics shows a connection between the models, and really a big variety of discrete structures also including programs. So, there's a lot of mathematical analysis and knowledge beyond the basic hypothesis that anytime your program's going to satisfy a power law, so at least for the moment, let's assume that. So now, if that's the case, I think the running time of my program is proportional to a constant times N to another constant. What I want to do is take advantage of that, and there's a consequence, and that consequence of that is if I take the ratio of the running time for a value N and twice that value, then it's going to be two to the b and you just plug in a times 2N to the b over a times N to the b. Everything cancels except for two to the b. So, you take the ratio of the running time as you're doubling N that's going to approach a constant, and we don't even need to calculate a to find out how fast the running time is growing. In calculating a, was something that was pretty complicated, and that was the thing that depended on the machine anyway. So, here's the method that we're going to use to figure out how fast the running time of a program is going to increase. So again, we start with a moderate size, take the running time, double the size, repeat while you can afford it, and then just take the ratios of the running times and verify that they approach a constant. You can extrapolation once you know that constant. Then, you can just multiply to estimate the running time. So, like in our 3-sum example. Again, we run it for 2,000. Ratio of our running times is eight. For 4,000 and 7.75, it's about eight, and that checks with our math model because two cubed equals eight, so b equals three. So, the running time should be proportional to a constant times two cubed. But the thing is if we now run it for 16,000 and it took four minutes to solve it for 8,000, we can figure out that the running time for 16,000 is going to be eight times that four minutes or about a half hour. So, while you're waiting for it to run, just look at the ratios of the previous running time and just multiply by that to figure out what the next running time. Then, you can just go right ahead and multiply, in this case, by eight to the seven to get your predicted running time for a million. That's a very simple method for estimating how long your program is going to take for a large number of inputs. So, that is the bottom line is it's often really easy to meet the challenge of predicting performance. Run this doubling method, figure out what the ratio is, and then extrapolate. That's something you can do for any program that you run. It's a lot easier. While you're waiting for the program to finish, you might as well do this, and you'll have a much better understanding of it. Now, if we ignore the constant a, what we're talking about it's what's called the order of growth of a function. Generally, we think of the order of the growth as a property of the algorithm, not the computer or the system, that is that constant a is different on an old computer, old system, new computer, new system, and might be lower, but really the method that we're using to solve the problems going to determine that order of growth. Again, we know that from experimental validation, ran the program 50 years ago and run it now, I still get the same order of growth we expect. If you have a computer that's x times faster and you run the same program, it should finish x times faster. Also, when we're doing the mathematical model, the thing that depend on the machine and the system is all constants. So they all roll up into one big constant, so the order of growth, that's not a property of the computer or the system. That's useful way to think about it because it means we can classify algorithms or methods that we use to solve problems by their order of growth. Again, for many programs, we know the order of growth or the running time is N to a power times log N to some other power. Here, we use log instead of log base two because we're in the constant it doesn't matter. So, and these immediately follow sometimes from the structure of the program. For example, if you have a program that's simply a for loop that's going through something N times, then that's running the order of growth of the running time of that program is going to be proportional to N and we call that linear. If you have nested for loops, again, with constant stuff going on inside, then that's going to be proportional to N-squared, we call that quadratic. Or triple for loops it's N-cubed and that's what we saw for ThreeSum but this applies to many, many other programs. If we have something like the convert program, that converts a number to binary and we see plenty of algorithms like this, where we solve a problem by solving. Doing some work and solving a problem half the size, then we get log N performance. If we do two problems of size N over two then we get N log N performance. We'll see examples of these later on. If we do two problems of size N minus one, then we get exponential performance. Those types of algorithms we can't run for very big N but that might as well put them on for the categories categorization. So, we think of algorithms as falling into these general categories. Again, many, many algorithms have been studied both empirically and mathematically and we know that indeed, they do. It's important to be aware. We'll see some examples later on. It's really important to be aware of these. So, the slope of the line is going to be the exponent of N. You see the log factor doesn't make that much difference, they're very close. What makes a difference is the exponent of N. This is in the log-log plot. Then the factor for the doubling method is just two to the slope or two to the exponent. So, what that says if the input size doubles, that's the factor that you multiply by to get the increase in running time. So, it's very important to know these general parameters because you'll see them for many of the programs that you write. If you run your program and take the ratio of running times and it seems like it's going to four then you can say okay it's quadratic. There's not many other cases than these, so it's good to know these classifications. Can look in more detail but certainly you want to have that idea. So, if you have a map model that tells you the order growth, we can use a doubling method to validate it or if you don't, you just use the doubling method to get a good estimate of the order of growth. That analysis should be done for any program that's trying to solve a large problem where performance is an issue. There's a really important implication of this, because we have this idea called Moore's Law, that's held for many decades now. Whereas, says that computer power that we have increases by roughly a factor of two every two years. But the thing is, when the computer power increases, say the speed of the computer also the size of the memory increases, and that means the size of the problem that you want to attack also doubles. So, the question is, when that happens, what's the effect on what you're going to spend to get your problem solved? This is a very common situation. You get a bigger computer, you fill it with a bigger problem, say weather prediction or bank processing transactions or cryptography. Certainly, you get a faster computer with more memory. You're going to want to load up the memory and solve the bigger problem. But if you just do this simple Math, you'll see what goes on. So, if my running time say is aN-cubed today, say the ThreeSum problem, then in two years, I get a computer that's twice as fast, so, that means the running time is A over two times the number my problem is twice as big, so it's 2N-cubed. So, to solve that, it's going to take four times as long to solve my problem in two years. It's a bigger problem but it's going to take four times as long. So, if you just look at this four common orders of growth for different problems. If I have a linear or an N log N algorithm, it's going to cost me about the same to solve my bigger problem with my bigger faster computer in two years. But if I have a quadratic algorithm, it's going to cost me twice as much. Or if I have a cubic algorithm, it's going to cost me four times as much. Four years from now, it's going to cost me 16 times as much if I have a cubic algorithm. This is an unexpected effect because budgets, people's budgets don't go up at this scale, and it means that the person who's using a linear or an N log N algorithm is still going to be able to get the job done. They're progressing with Moore's Law. They're following technological progress and getting bigger problems solved with their bigger faster computers. But if you're using a quadratic or cubic algorithms, you're not, you're falling behind by a factor of two or four every two years. You absolutely can't afford to use a quadratic algorithm or worse, to address an increasing problem size and that's a very important insight for everyone developing software to attack large problems at a half. So, this is just a summary of meeting the challenge. Here's Bob again, who went to the Hackathon. He says, "Well, my program's not finished yet. I think I will go get a pizza." Alice says, "Well, mine's taken too long to run but I think I'll run a doubling experiment." Bob comes back from his pizza and still running, and Alice said, "Well, it showed that I had a higher order growth than I expected. So, I found it and fixed the bug. Now, I'll go get pizza." So again, if you have an understanding of what your program is doing, then you can easily get that with good insight with doubling experiments. It's something that you really should do. The best practice is to have some realistic experiments for debugging, anyway. So, you might as well get some idea about performance and that's way better than having no idea. Absolutely, performance matters in really quite a few situations. Now, there were plenty of caveats. The story is not always as simple as I've laid out. Sometimes, we can't really meet the challenge of predicting performance. Well, like as I mentioned before, maybe there's other apps running on the computer. What about the log factor? Well, actually the log factor doesn't matter in the long run. You still get the doubling ratio associated with the exponent of N. What about my computer's got a cache, it's got movable processors? Your models to simple. Well, we'll make the model more complicated. What about if I have N log N plus 100N that needs to be more terms maybe? Yeah. Well, we can refine the model and that way. What happens if the leading term oscillates? You said it was a constant. Actually there's cases that we know where the term oscillates and a algorithm analysts would say you should be lucky to get that one because that's a really interesting program to study. Or maybe your input model is too simple. My real input data is totally different. Well, you should get an understanding of what your input is then. But still, it's true that the doubling method that we've outlined is very simple and it's robust in the face of many, many of these challenges. So, these are not reasons to avoid it, go ahead and use it and maybe use it to uncover one of these caveats. In a lot of times, it'll be strong enough to go right through.
