Observing what's happening as we did in the last section, gives us a way to predict performance but it really doesn't help us understand what the algorithms are doing. So next, we're going to look at mathematical model, a way to get a better concept of what's really happening. Again, this concept was really developed and popularized by Donald Knuth starting in the late 60s. At that time, computer systems were really becoming complicated for the first time. And, computer scientists were concerned about whether we really were going to be able to understand what's going on. And, Knuth was very direct in saying that this is something that we certainly can do. We can calculate the total running time of a program by identifying all the basic operations, figuring out the cost, figuring out the frequency of execution, and summing up the cost times frequency for all the operations. You have to analyze the program to determine what set of operations and the cost depends on the machine and the computer in the system as well- we talked about before, the frequency leads us to mathematics because it depends on the algorithm and the input data. Knuth has written a series of books that give very detailed and exact analyses within a particular computer model for a wide range of algorithms. So, from Knuth, we know that in principle, we can get accurate mathematical models for the performance of algorithms or programs in operation. All right. So, what does this process look like? Well, you can, if you want, run experiments in ancient times, we would actually look at the computer manual and every computer came with a manual that said precisely how long each instruction would take. Nowadays, it's a little more complicated so we run experiments. And, you can go ahead and do a billion ads and figure out that maybe on your computer, an ad takes 2.1 nanoseconds. Or, you can do more complicated functions like computer sign or an arctangent, although that's already getting close to the analysis of algorithms. So, there's some way to determine the cost of the basic operations. And so, we'll just in most of the cases, we'll just postulate that it's some constant, and you can figure out what the constant is. Although, when we're working with a collection of objects of N objects, there's some things that take time proportional to N. Like, if you're going to allocate a array of size N, it takes time proportional to N because in Java, the default is that all the elements in the array are initialized to zero. In other operations, it depends on the system implementation. And an important one is string concatenation. If you concatenate two strings, the running time is proportional to the length of the string. In many novices, programming and Java make the mistake of assuming that that's a constant time operation, when it's not. All right. So, that's the cost of each operation. More interesting, is the frequency of operation of execution of the operations. So, this is a very simple variant of a three sum problem that's the one sum problem, that's how many numbers are actually equal to zero, how many single numbers add up to zero. So, that one is just one four loop, and we go through and we test if the number is zero and increment our count. And, by analyzing that code, you can see that i and count have to be declared, there and then they have to be assigned to zero. There's a comparison of i against N and there's N plus one of them, there's compares of a of i against zero, there's N of those, N array accesses. In the number incremented, is a number of times as an increment is variable, i is incremented N times but count could be incremented to any number from zero to N times. And so, that frequency is dependent on the input data or we might need a model for describing that. Or maybe, there's other operations that are more expensive and we won't need to worry about that. So, let's look at next more complicated problem is, what about the frequency of execution of instructions in this program, which is the two sum problem? How many pairs of integers sum to zero? Well, in this case, you have to do a little bit of math to see that when we, when i goes from zero to N and j goes from i plus one to N, the number of compares that we do, or let's say array accesses that we do, is two for each time the if statement is executed for ai and aj. And that time- thing is executed, n minus one times the first time through the loop, and n minus two the second and so forth. It's the sum of the integers from zero up to N minus one which is a simple discrete sum one half N times N minus one and since we're doing it twice, the number of array accesses is N minus one. So, we can go ahead and get these actual exact counts. But already, it's getting a little bit tedious to do that. And, as far back as Turing, who also knew that as well as Babbage did, that we want to have the measure of the amount of work involved in the process, he recognized that you didn't want to necessarily go through and do it in full detail. It's still helpful to have a crude estimate. So, you could count up the number of times that every operation is applied, give it weights and count this abstract and so forth. But, maybe we should just count the ones that are most expensive. That's what Turing said in 1947. And realistically, that's what we do nowadays. So, rather than going in and counting every little detail, we take some basic operation that's maybe the most expensive and or and or the one that's executed the most often, and the one that costs time frequency is the highest, and use that as a proxy for the running time. Essentially, making the hypothesis that the running time is going to grow like a constant times that. So, in this case, we're going to pick array accesses. So, that's the first simplification. And the second simplification is, that we're going to ignore low order terms in the formulas that we derive. And, there's an easy way to do that, it's called the tilde notation. And the idea is, when N is large in a formula like this, the N cube term is much much higher than the N term or 16. In fact, so much so that we wouldn't even hardly notice these low order terms. So, all of these formulas are tilde one sixth N cubed, and that's a fine representative or approximate approximation to these quantities. And then it greatly simplifies the calculations to throw away the low order terms like this. So, by focusing on one operation and throwing away the tildes- the low order terms, and this is the technical definition of tilde, f(N)~g(N) means the limit is f(N) or g(N) equals 1. And you can check that that's going to hold in these kinds of situations. So, that greatly simplifies the frequency counts. And if we're only picking one thing, we're just talking about tilde N squared and maybe another tilde N squared for the anchor for the to sum problems. So again, when N is large the terms are negligible. When N is really small, they're not negligible. But, we don't really care because we're trying to estimate running time for large N and running time for small N are going to be small no matter what. All right. So now, we're using both the cost model and the tilde notation and then we can simply say that, this program uses tilde N squared array accesses and have implicit the hypothesis that we think the running time is going to be tilde, a constant times N square. Okay well, now what about a three sum? Let's do our real problem. So now, we have the triple loop and then we have to do a more complicated common notarial problem, and it's not that big a deal, really. We're looking at the distinct number of ways you can choose three things out of N, and that's a binomial coefficient. And again, doing the math and using the tilde, it's just tilde one sixth N cubed three array accesses for each triple. So, we can say half N cubed. So, we're not computing and summing the cost of all operations, that's too much work. We're picking the most expensive in terms of cost times frequency and approximating that and trying to get a good model for the running time. So now, most- we're not going to do a full discrete mathematics in this course. But there are some basic things that we'll want to use and are not that difficult to understand. So, a lot of times, we find out that we need to come up with an estimate of a discrete sum like we did for one plus two up to N, where, some of the squares or other things like the three sum triple loop. And so, actually if you've had a basic calculus, one way to think of it is to just replace the sum with an interval integral. That usually works or we can do the math and use the so called Euler-Maclaurin summation formula to get a true approximation. But if you think of it this way, you'll believe us when we say that that thing is still a half N square. Or, sum of one plus one half plus one third up to one over N, that's like integral from x equals one to N one over x and that's natural log of N. Now, even the three sum triple loop kind of, if you're used to multiple integrals, will quickly give you the one sixth N cubed. There's many more and other techniques that we can use for this. And, we're not going to teach all that. But, we'll sometimes refer to results of this type. All right. So, in principle, Knuth tells us that accurate mathematical models are available. In practice, we can get really complicated formulas. We also might need some advanced mathematics that the theoretician will revel in but that maybe people learning algorithms of the first time might not be expected to know. So, in the end, careful exact models are best left for exit- experts. There's really a lot of things that can go on. On the other hand, approximate models are definitely worthwhile. For all the algorithms that we consider, we'll try to communicate a reasonable approximate model that can be used to describe the running time. Sometimes, we'll give the mathematical proofs and other times we'll have to just site the work of some expert.
