0:02

In this sequence of lectures, we're going to learn Asymptotic Analysis.

Â This is the language, by which every serious computer programmer and

Â computer scientist, discusses, the high level performance, of computer algorithms.

Â As such, it's a totally, crucial, topic.

Â In this video, the plan is to segueway between the high level discussion that

Â you've already seen in the course introduction.

Â And the mathematical formalism which we're going to start

Â developing in the next video.

Â Before getting into that mathematical formalism,

Â however, I want to make sure that the topic is well motivated.

Â That you have solid intuition for what it's trying to accomplish, and

Â also that you've seen a couple of simple, intuitive examples.

Â Let's get started.

Â 0:44

Asymptotic analysis provides basic vocabulary for

Â discussing the design and analysis of algorithms.

Â And while it is a mathematical concept, it is by no means math for math's sake.

Â You will very frequently hear serious programmers saying that such and such code

Â runs in o of n time where such and such other code runs in o of n squared time.

Â It's important you know what programmers mean when they make statements like that.

Â 1:09

The reason this vocabulary is so ubiquitous is that it identifies a sweet

Â spot for discussing the high level performance of algorithms.

Â What I mean by that, is it is on the one hand,

Â coarse enough, to suppress all of the details that you want to ignore.

Â Details that depend on the choice of architecture,

Â the choice of programming language, the choice of compiler, and so on.

Â 1:34

On the other hand it's sharp enough to be useful.

Â In particular, to make predictive comparisons

Â between different high level algorithmic approaches to solving a common problem.

Â This is going to be especially true for large inputs.

Â And remember as we discussed in some sense, large inputs are the interesting

Â ones, those are the ones for which we need algorithmic ingenuity.

Â For example, asymptotic analysis will allow us to differentiate between better

Â and worse approaches to sorting.

Â Better and worse approaches to multiplying two integers and so on.

Â 2:10

Now most serious programmers if you ask them,

Â what's the deal with asymptotic analysis anyways?

Â They'll tell you reasonably, that the main point is to suppress

Â both leading constant factors and lower order terms.

Â 2:24

Now, as we'll see, there's more asymptotic analysis than just these seven words here.

Â But long term,

Â ten years from now if you only remember seven words about asymptotic analysis,

Â I'll be reasonably happy if these are the seven words that you remember.

Â So how do we justify adopting a formalism which essentially by definition,

Â suppresses constant factors and lower order terms?

Â Well lower order terms basically,

Â by definition, become increasingly irrelevant as you focus on large inputs.

Â Which, as we've argued,

Â are the interesting inputs, the ones where algorithmic ingenuity is important.

Â As far as constant factors, these are going to be highly dependent on

Â the details of the environment, the compiler, the language and so on.

Â So if we want to ignore those details, it makes sense to have a formalism

Â which doesn't focus unduly on leading constant factors.

Â 3:14

Here's an example.

Â Remember when we analyzed the merge sort algorithm,

Â we gave an upper bound on its running time that was 6 times n log n plus 6n.

Â Where n was the input length, the number of numbers in the input array.

Â So the lower order term here is the 6n.

Â That's growing more slowly than than n log n, so we just drop that.

Â And then the leading constant factor is the 6 so we suppress that as well.

Â After those two suppressions we're left with a much simpler expression, n log n.

Â 3:44

The terminology would then be to say that the running time of merge sort is big O

Â of n log n.

Â So in other words,

Â when you say that an algorithm's running time is big O of some function.

Â What you mean is that after you've dropped the lower order terms, and

Â suppressed the leading constant factor, you're left with the function f of n.

Â Intuitively, that is what the big O notation means.

Â So to be clear, I'm certainly not asserting thay

Â constant factors never matter when you're designing and analyzing algorithms.

Â Rather, I'm just saying that when you think about high level

Â algorithmic approaches, when you might want to make a comparison between

Â fundamentally different ways of solving a problem.

Â Asymptotic analysis is often the right tool for

Â giving you guidance about which one is going to perform better.

Â Especially on reasonably large inputs.

Â Now, once you've committed to a particularly algorithmic solution to

Â a problem.

Â Of course, you might want to then work harder to improve the leading constant

Â factor, perhaps even to improve the lower order terms.

Â By all means if the future of your start up depends on how efficiently you

Â implement some particular set of lines of code, have at it.

Â Make it as fast as you can.

Â In the rest of this video I want to go through four very simple examples.

Â In fact these examples are so simple, if you have any experience with big O

Â notation, you're probably better off just skipping the rest of this video.

Â And moving on to the mathematical formalism that we begin in the next video.

Â But if you've never seen it before,

Â I hope these simple examples will get you oriented.

Â 5:37

That is the code just checks each array entry in turn.

Â If it ever finds the integer t it returns TRUE.

Â If it falls off the end of the array without finding it, it returns FALSE.

Â So what do you think?

Â We haven't formally defined big O notation, but

Â I've given you an intuitive description.

Â What would you say is the running time of this algorithm

Â as a function of the length of the array, capital A?

Â 6:12

Why is that true?

Â Well let's think about how many operations this piece of code is going to execute.

Â Actually the lines of code executed is going to depend on the input.

Â It depends on whether or not the target t is contained in the array A.

Â And if so, where in the array A it lies.

Â But, in the worst case this code will do an unsuccessful search.

Â T will not be in the array and the code will scan through the entire array A and

Â return FALSE.

Â The number of operations then is a constant.

Â There is some initial setup, perhaps and

Â maybe it's an operation to return this final bullying value.

Â But outside of that constant, which will get suppressed in the big O notation,

Â it does a constant number of operations per entry in the array.

Â And you can argue about what the constant is,

Â if it's two, three, four operations per entry point in the array.

Â But the point is, whatever that constant is two, three, or four,

Â it gets conveniently suppressed by the big O notation.

Â So as a result, the total number of operations would be linear in n, and

Â so the big O notation will just be o of n.

Â 7:17

So that was the first example.

Â In the last three examples,

Â I want to look at different ways that we could have two loops.

Â And in this example, I want to think about one loop followed by another, so

Â two loops in sequence.

Â I want to study almost the same problem as the previous one.

Â Where now we are just given two arrays, capital A and capital B,

Â let's say both are the same length.

Â And we want to know whether the target t is in either one of them.

Â Again, we'll look at the straight forward algorithm that we just searched through a.

Â And if we fail to find t and a, we search through b.

Â If we don't find t and b either, than we have to return return FALSE.

Â 8:05

Well, the question was the same and in this case the answer was the same.

Â So this algorithm, just like the last one, has running time big O of n.

Â If we actually count the number of operations

Â of course it won't be exactly the same as last time.

Â It'll be roughly twice as many operations as the previous piece of code.

Â That's because we have to search two different arrays each of link in.

Â So, whatever work we did before we now do it twice as many times.

Â Of course that two being a constant.

Â Independent of the input length n,

Â is going to get suppressed once we passed a big O notation.

Â So this, like the previous algorithm, is a linear time algorithm,

Â it has running time big O of n.

Â Let's look at a more interesting example of two loops,

Â where rather than processing each loop in sequence, they're going to be nested.

Â In particular, let's look at the problem of searching whether two given input

Â arrays each of link n, contain a common number.

Â 9:06

The code that we're going to look at for solving this problem is the most

Â straight forward one you can imagine, where we just compare all possibilities.

Â So for each index i into the array a, each index j into the array b.

Â We just see a if A[i] is the the same number as B[j].

Â If it is we return TRUE.

Â If we exhaust all of the possibilities without ever finding equal elements,

Â then we're safe in returning a FALSE.

Â 9:45

So this time the answer has changed.

Â For this piece of code the running time is not big O with n, but

Â it is big O of n squared.

Â So, we might also called this a quadratic time algorithm.

Â Because the running time is quadratic in the input length n.

Â So, this is one of those kinds of algorithms where if you double

Â the input link.

Â Then the running time of the algorithm will go up by a factor of four

Â rather than by a factor of two, like in the previous two pieces of code.

Â So why is this?

Â Why does it have quadratic running time big O of n squared?

Â Well again,

Â there's some constant setup costs which gets suppressed in the big O notation.

Â Again, for each fixed choice of an entry i into array A and an index j for array B,

Â for each fixed choice of i and j, we only do a constant number of operations.

Â The particular constants are relevant because it gets suppressed in the big O

Â notation.

Â What's difference is that there's a total of n squared

Â iterations of this double four loop.

Â In the first example we only had n iterations of a single four loop.

Â In our second example because one four loop completed before the second one

Â began we had only 2n iterations overall.

Â Here, for each of the n iterations of the outer four loop,

Â we do n iterations of the inner four loop.

Â So that gives us the n times n, ie n squared total iterations.

Â So that's going to be the running time of this piece of code.

Â 11:21

So here's the piece of code we're going to analyze for solving this problem, for

Â detecting whether or not the input array A has duplicate entries.

Â There's only two small differences relative to the code that

Â we went through on the previous slide when we had two different arrays.

Â 11:36

The first change won't surprise you at all which is instead of referencing

Â the array B, I change that B to an A.

Â All right, so

Â I'm just going to compare the i th entry of A with the j th entry of A.

Â The second change is a little bit more subtle.

Â Which is I changed the inner for loops so that the index j begins at i plus one.

Â Where i is the current value of the outer four loop's index,

Â rather than starting at the index one.

Â I could have had it start at the index one, that would still be correct, but

Â it would be wasteful and you should think about why.

Â If we started the inner four loops index at one, then this code would actually

Â compare each distinct pair of elements of A to each other twice.

Â Which of course is silly.

Â You only need to compare two different elements of A to each other once,

Â to know whether they're equal or not.

Â So this is the piece of code, the question is the same as it always is.

Â What in terms of big O notation and

Â the input link n is the running time of this piece of code?

Â 12:35

So the answer to this question, same as the last one, big O of n squared.

Â That is this piece of code is also has quadratic running time.

Â So what I hope was clear was that whatever the running time of this piece of code is.

Â It's proportional to the number of iterations of this double four loop.

Â Like in all the examples, we do constant work per iteration.

Â We don't care about the constant, it gets suppressed by the Big O notation.

Â So all we gotta do is figure out how many iterations there

Â are of this double for loop.

Â My claim is that there's roughly n squared over two

Â iterations of this double four loop.

Â There's a couple ways to see that.

Â Informally we discussed how the difference between this code and the previous one,

Â is that instead of counting something twice, we're counting it once.

Â So that saves us a factor of two in the number of iterations.

Â Of course, this one half factor gets suppressed by the big O notation anyways.

Â So the big O running time doesn't change.

Â A different argument would just say, there's one iteration for

Â every distinct choice of i and j of indices between one and n.

Â And a simple counting argument says that there's

Â n choose two such choices of distinct i and j.

Â Where n choose two is the number n times n minus one over two.

Â And again suppressing lower order terms in the constant factor,

Â we still get a quadratic dependence on the length of the input array A.

Â 13:52

So that wraps up some of the sort of just simple basic examples.

Â I hope this gets you oriented, you have a strong intuitive sense, for what Big O

Â notation is trying to accomplish, and how it's defined mathematically.

Â Let's now move on to both the mathematical development and

Â some more interesting algorithms.

Â