0:01

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.

Â