algo0201

7.651 Um. So my name is Erik Demaine. You should call me Erik. Um, Welcome back to 6.046. This is lecture 2.

My name is Erik Demaine. You should call me Erik. Welcome back to our course. The course number is 6.046. This is lecture 2.

You should call me Erik. Students often call younger professors by their first name.

17.467 Um, and today we're going to essentially fill in some of the more mathematical underpinnings of Lecture 1.

Lecture 1 introduced some ideas that have mathematical background. It left out that background. Today we are going to fill in some of that background. This is, essentially, what we are going to do today. In short summary, we are going to fill in the mathematical underpinnings of the material of Lecture 1.

essentially in essence, in summary. This adverb is often overused, or used as a filler that does not contribute much to the meaning. It is used correctly here, to mean "in summary, giving only the most important point."

26.628 So Lecture 1: we just sorta barely got our feet wet with some analysis of algorithms and insertion sort and merge sort; and we needed a couple of tools, we had this big idea of asymptotics, and forgetting about constants, just looking at the lead term. And so today we're going to develop asymptotic notation, to really, uh, so that we know that mathematically.

In Lecture 1, we just started, in a very small way, with some analysis of algorithms. We barely started with it. We barely got our feet wet. We looked at insertion sort and merge sort. We realized we needed a couple of tools. We had this big idea of asymptotics: drop the constants and low-order terms, only look at the lead term. Today we will develop precise formal asymptotic notation. Our goal is to understand mathematically what the big idea of asymptotics means.

Lecture 1 should be In Lecture 1.

we had this big idea The word this here means something like "We had an idea under discussion, and I'm going to bring it to the center of our attention and remind you what it is."

45.8 And we also ended up with a recurrence with merge sort, the running time of merge sort, so we need to see how to solve recurrences.

Another unfinished item from lecture 1: we looked at merge sort and developed a formula for its running time, and it was a recurrence equation. So today we will learn how to solve recurrences.

end up with X arrive at X, perhaps unexpectedly, after some process.

52.39999999999999 And we'll do that, those two things today. Question.

These are the two things that we will do today. Question?

Question? This is a common way to invite a student to ask his or her question. Often accompanied by a pointing gesture.

55.8

Uh, Can you speak up just a little bit please?

(Student) Could you speak a little louder, please?

speak up speak louder

56.66699999999999 Yes, I will speak louder. Thanks.

Yes, I will speak louder.

Thanks. This is a good positive word to say. It means something like: "Thank you for pointing out to me that I am not speaking loudly enough. I am not at all offended by your saying so. It was useful for all of us because I will speak louder and you will be able to hear me better."

59.133 Good. Even though I have a microphone, I am not amplified. Good. Ok, so let's start with asymptotic notation.

Good. I do have a microphone, but it looks like I am not amplified. Good. So, let us start with asymptotic notation.

Good. This is another good positive word to say. It means: "We are making progress. We have solved this small problem with my speaking too softly, and we can now move on to the subject matter of the lecture."

68.8 So, we've seen some basic asymptotic notation. I'm sure you've seen it in other classes before. Things like Big O Notation.

We have seen some basic asymptotic notation. I am sure you have seen it before, in other classes. For instance, you have probably seen the Big O Notation.

things like X The X itself or something similar to it.

84.133 And ... today we're gonna really define this rigorously so we know what's true and what isn't ... what's valid ...what isn't.

Today, we are going to define asymptotic notation rigorously. After we do that, we can prove things mathematically. In mathematics, the idea of truth is more precise than outside mathematics. So, in mathematics you really know what is true and what isn't. After we define asymptotic notation mathematically, we will know what is true and what isn't about it.

Another word that has a precise meaning in mathematics is valid. It has to do with logical conclusions. So, after we define asymptotic notation mathematically, we will know what conclusions are valid and what conclusions are not valid.

rigorously In scientific contexts, this often means "mathematically; using a mathematical definition or proof."

96.133 OK ... So ... We're gonna define ...and uh, unfortunately today is going to be really mathematical ... and really no algorithms today, which is sort of a anti-climax, but next lecture we'll talk about real algorithms and we'll apply all the things we learned today, to real algorithms.

So, we are going to define ... Before I tell you what we are going to define, I want to warn you and to apologize that today's lecture will be very mathematical. We will not talk about algorithms today. So it may be less interesting or exciting that lecture 1. It may be a step down in interest from lecture 1. However, in the next lecture we will talk again about real algorithms. We will learn important mathematical things today. We will apply them to real algorithms in the next lecture.

unfortunately, today is going to be really mathematical The lecturer assumes that the students are more interested in algorithms and programs than in mathematics.

anticlimax a disappointing decline after a previous rise

118.133 So ... this is Big O Notation, capital O Notation. So we have f(n) equals O(g(n)). This means ... that ... there are some suitable constants, uh, C and N_0 such that f is bounded by C*g(n) ...

Here is Big O notation. Big O means "capital letter O." So it is capital O notation: f(n) = O(g(n)). This means that there are two constants, C and n-sub-0 (n₀) such that the function f is bounded by C*g(n)...

INSERT SLIDE HERE

n-nought same as n-zero, n sub zero. nought is an old way to say nothing; it is used in some expressions such as "All our efforts came to nought."

153.467 for all sufficiently large n. OK, so this is a pretty intuitive notion, we've seen it before. We're gonna assume that f(n) is, uh, non negative here, and I just want f(n) to be bounded above by g(n).

for all n that are greater than n₀, or for all sufficiently large n. This is a pretty intuitive notion. It makes sense. It is pretty easy to understand. We have seen it before. We will assume that f(n) is non-negative, f(n)>= 0. I want f(n) to be less than g(n) for all n. We say: f(n) is bounded from above by g(n).

intuitive notion Something that is not too abstract and can be understood by an analogy or real-life intuition. (NB: this meaning of intuitive is not in WordNet)

I want f(n) to be bounded I want X to be Y "I want it to be true that X is Y. We want you to be happy.

170.06700000000004 So, we, I'm, we've seen a bunch of examples, but something like, uh ... 2 times n squared is big O of n cubed, OK, fine. Um, and, roughly this means that if you drop, uh, leading constants and low order terms than this is less than or equal to that. So Big O corresponds roughly to less than or equal to. Um, but this is the formalization.

We have already seen a few examples, but here is another one: 2*n² = O(n³). Approximately, this means that if you drop leading constants and low-order terms, then the function on the left side is less than or equal to the function on the right: n² <= n³. So, Big-O roughly corresponds to "less than or equal to." But what we have just said is a precise formal statement. It is the formalization of that rough correspondence.

a bunch of several, a number of. Used in informal speech. Erik's mathematics is quite formal, but his English is very informal.

roughly approximately, in rough (not precise) terms. This is the meaning of rough that is the opposite of fine-grained, precisely formed.

then... than Many English speakers confuse these two words in writing. then is used with if: if X then Y. It is also an adverb of time: It was X, then it was Y means "X was followed by Y." Than is used in comparisons: X is less than or equal to Y. You are happier today than you were yesterday.

195.73300000000003 Another way to think of it, formally as uh, So a funny thing about this notation is it's asymmetric. Normally you think of a equality being symmetric. A equals B, then B equals A, but it's not true here. We don't have n cubed being Big O of, of n squared. You don't even have Big O of n cubed equaling n squared, so we'll, we'll see exactly what that means in a second ...

We can also think of it formally as ... (Sentence abandoned in order to give more background before presenting another formal notation). A funny thing about this notation is that the equal sign in it is asymmetric. Normally, equality is symmetric: if A equals B, then B equals A. This is not true here. It is not true that n³ = O(n²). We don't have n³ being O(n²). You don't even have O(n³) = n². So what does this equal sign mean if it is not symmetric. We will see what it means in a second..

a funny thing about X an unusual thing about X; an unusual feature of X. There is nothing really funny about the Big-O notation.

217.40000000000003 But, before we get there ... So, this is a bit bizarre notation, and you should always think about what it really means.

But before we get to see what it means ... (Sentence abandoned in order to summarize what had just been said.) So, this Big-O notation is strange. It is a little bizarre. When you work with it, you should always think about what it really means.

get there This expression is often used to refer to a sequence of ideas or actions, rather than movement in space. How do we get there? may mean "How do we achieve this conclusion, or this goal?"

bizarre very strange

229.06700000000004 Um, another way to think about what it really means is that f(n) is in some set of functions that are like g.

Now I return to another way of thinking about Big-O. Another way to think about it is that f(n) is in some set of functions that are like g.

what it really means Big-O notation has an equal sign in it. However, this is equal sign does not really mean equality. What it really means...

237.73300000000003 So, you could define Big O of g(n) ... to be a set of functions, let's call it ... {f(n)}such that ... there exist constants ...it's the same definition ... nothing fancy here ... C and N_0 such that we have the bounds, f(n) is between zero and C*g(n).

You could define Big O of g(n) to be a set of functions. Let us call it f(n), in curly brackets. The set consists of functions f(n) such that there exist constants... For each f(n) in the set, it is the same definition as before. We are not doing anything difficult or elaborate or fancy here. The constants C and n₀ are such that we have the bounds, f (n) is between zero and C*g(n). (Close the curly bracket.)

INSERT SLIDE HERE

fancy When said about ideas rather than clothes, this adjective means "complex; elaborate; perhaps more complex than is necessary."

269.733 OK, so a bit of a long definition and that's why we use the notation, to avoid having to write this over and over.

This definition is a bit long. This is a bit of a long definition. That's why we use the notation. We use the notation so we don't have to write a long definition over and over again. We use the notation to avoid doing that.

avoid doing X manage not to do X, even though it may be difficult to avoid doing it. The verb avoid requires a direct object: We barely avoided a collision with another car. In this case, the direct object is a gerund phrase.

over and over Many times. Often used in the form over and over again.

279.6000000000001 Um, so, you can think of instead of n squared being equal to Big O of n cubed, what we really mean is that two n squared is in the set Big O of n cubed.

When we say: "n² is equal to O(n³)" what we really mean is: "2*n² is in the set O(n³)." (2*n² ε O(n³)) This is how you can think of the Big-O notation.

instead of X being equal to Y Another example of a gerund phrase, in the context where a noun phrase is required, after the preposition of.

in the set The Greek letter ε is the standard symbol for the in-the-set relation.

290.2000000000001 So, this, when we write equal sign, we in some sense mean, um, this in the set. But we're gonna use equal sign. You could write this, and occasionally you see papers that write this, but ... this is the notation that, that we're gonna use.

When we write this formula, with the equal sign, we mean this formula, with the Greek letter ε, which means "in the set." You could write the Big-O formula this way, with ε. There are papers that use this notation. Occasionally you see such papers. But this notation with the equal sign is the notation that we are going to use.

You could write this This is less strong than You can write this. If Erik used the form can, he would be saying: "You can use either of the two formulas, we don't care." Instead he says: "You could, in some hypothetical situation, write this, and people would understand you, but please don't."

306.2000000000001 So that has the consequence that equal sign is asymmetric, just like this, uh, operator.

OK, we have ... some nifty ways that we actually use Big O notation.

This explains why the equal sign in the Big-O formula is asymmetric. The equal sign really stands for the ε operator. It expresses the in-the-set relationship. That relationship is asymmetric. This has the consequence that equal sign is asymmetric, This has the consequence of equal sign being asymmetric.

It is time to start using Big-O notation. There are really wonderful, interesting, elegant ways to use that notation.

X has the consequence Y Y is the consequence of X. X is the reason for Y.

Grammar topics:

direct objects with infinitives: want X to Y
then and than
gerunds

Expressions:

get used to; some kind of; rearranging furniture on the Titanic; sort of (as an adverb); a bunch of; can't tell, the whole idea; figure out

Vocabulary:

arrange, rearrange, arrangement, rearrangement; rearranging furniture on the Titanic; pseudocode; shorthand; means (singular noun); keep (doing)

CS terminology :

algorithm; pseudocode; invariant; set (X to Y); nest, nesting;