Preceded by: insertion sort; example; transition to analysis
We will mostly focus on the kind of analysis that is called "worst-case analysis." This is the most common kind of analysis. This is the kind of analysis that we usually do. In worst-case analysis, we define T(n) to be the maximum time on any input of size n. So it's the maximum it could possibly cost us to run the algorithm on an input of size n.
this is what we do usually a reference to what is being written on the blackboard
The lecturer repeats important concepts two or three times.
The maximum it could possibly cost us What is "it" here? The action of running the algorithm on an input of size n.
The one one is an indefinite pronoun here, referring to kinds of analyses.
the maximum input He means "the maximum-time input, the input that takes the most time within inputs of the same size."
If you look at the differences between inputs -- if you take into account that sometimes the inputs are better [and take less time], and sometimes they are worse [and take more time], [you will realize that] we're looking at the worst case and the maximum time because we want to make a guarantee that [within that time] the algorithm will always (on all inputs) do something, rather than only sometimes (on some inputs) do something. That's why we look at the maximum.
what that does is... One of many unfinished sentences that could have been: What that does is it makes it possible for us to give a guarantee.
the fact that An expression that converts a clause into a noun phrase. There are usually better ways to express what you want to say. Two possible strategies are: (1) use the same verb followed by a noun phrase that summarizes the clause; (2) use a verb that can be followed directly by a sentence, such as take into account. Both strategies are illustrated in the paraphrases.
Note that if I didn't have maximum, T(n) would be a relation, not a function, because the time on an input of size n [could have many different values because] it depends on which input of size n [is given]. But by putting the maximum on it, we turn it (it=T(n)) into a function because there is only one maximum time that it (it=the algorithm) will take.
if I didn't have maximum ...T(n) is a relation The lecturer starts with a counter-to-fact condition but continues in the Present tense. This is sloppy and should never be allowed in writing.
relation... function You need to know these terms to understand what he is saying.
By putting the maximum on it, it turns a relation into a function.. This is also sloppy. The implied subject of putting is we, and it should be the subject of the main sentence: By putting the maximum on it, we turn the relation into a function.
Putting is similar to both a noun and a verb. Like a noun, it can follow a preposition (by putting...). Like a verb, it can have a direct object (putting a maximum on it). Such forms are called gerunds, and the entire phrase is called a gerund phrase.
Sometimes, we will do average case analysis. So sometimes we will define T(n) to be the expected time of algorithm over all inputs of size n. If I talk about expected time, what else do I need to say? What does "expected time" mean? (Speaking to a student) I'm sorry? Raise your hands so I can see who is talking. (Repeating a student's words) "Expected inputs" - what does it mean, "expected inputs"? I need a more mathematical answer. What do I mean by expected time here?
sometimes we'll do this This is the beginning of the next "section" of the lecture. The previous section started with This is what we do usually We see a contrast between "do usually" and "do sometimes.".
I'm sorry (or Excuse me or I beg your pardon) These apologies, with a specific intonation, mean "I haven't heard what you said, please repeat."
(Pointing) Over here. (Repeating after the student; note the "quoting" intonation.) You have to take the time of every input and average them. That's kind of what we mean but not quite. What you say is completely correct except it's not enough. (Pointing) Yes? (Repeating) It's the time of every input times the probability of that input. This is called "the weighted average." But how do I know what the probability of every input or a particular input is? I don't!
You have to take the time of every input and then average them. The lecturer always repeats what the student says so everybody in the lecture room can hear. See also below: It's the time of every input times the probability that it will be that input.
OK, That's kind of what we mean... Good. Not quite The lecturer tries to be positive and encourage the students. Even when he has to say No, he says Not quite instead.
What you say is completely correct except it's not enough Another example of being positive.
I have to make an assumption. What is that assumption called? What kind of assumption do I need to make? I need an assumption of the statistical distribution of inputs.
make an assumption One of several expressions with the verb make:
suggest - make a suggestion
propose - make a proposal
Otherwise, without such an assumption, expected time doesn't mean anything because I don't know what the probability of each data item is. In order to calculate with probabilities, you need some assumptions.
You've got to state those assumptions clearly. One of the most common assumptions is that all inputs are equally likely. That kind of the statistical distribution is called the Uniform Distribution. Every input of size n is equally likely.
you've got to same as you have to but more emphatic. For even more emphasis, use the full form: you have got to
that kind of thing. The lecturer repeats an important concept, feels a need to do more than simply repeat what has just been said, and adds a phrase that doesn't mean much.
dealing with expectations and stuff A number of general words in this phrase
deal with X "take some unspecified action with respect to X such that the problem having to do with X will be solved or closer to solving"
they may not all be be true What does it mean for a statistical distribution to be true or not true? Some statistical distributions describe the probabilities of input much better than others: some of them are true, others are false.
much more complicated More complicated than what? He doesn't say. Probably:" more complicated than the worst-case analysis."
and stuff an informal way of saying and so on.
if you don't (have a strong probability background)
Gee! An exclamation that may mean surprise at learning or discovering a new idea.
The last kind of analysis I want to mention is the best case analysis, and this, I claim, is bogus. Why is it bogus? [A student says:] "The best case probably doesn't ever happen." This suggestion points to an interesting fact: it is very common that things that get sorted by a sorting algorithms are things that are already sorted [which is the best case for insertion sort]. So for example (interrupts to correct himself) or things that are almost sorted.
bogus fake, phony, pretending to be something it is not
Umm The intonation clearly suggests that the lecturer disagrees with the student.
Actually, that's interesting, because... Instead of saying "You are wrong" the lecturer points to an interesting fact that contradicts the student's answer. In effect, he turns the student's answer into a question ("Does the best case every happen?") and it turns out that the best case for insertion sort does happen, often.
get sorted... are sorted The first occurrence of sorted describes the action of sorting; the second occurrence describes the condition that results from such an action.get sorted... are already sorted The word sorted in get sorted refers to the action of sorting. The word sorted in are sorted refers to the condition of being in order. Some things are sorted because they have been sorted. Other things are sorted naturally, before any algorithm sorts them.
the vast majority of what's going on Usually, the expression the vast majority of is followed by a countable noun in the plural: the vast majority of inputs.
Doesn't really do much for you. There is no subject in this sentence, and the phrase for you is pronounced with the emphasis on the preposition: FOR ya. The lecturer is imitating a very informal manner of speaking.
Grammar topics:
Expressions:
the fact that; look at (an abstract thing); the same thing; we're done (are you done?); take (time duration);
Vocabulary:
thing; stuff; depend on;
CS terminology :
loop, inner loop, outer loop, loop invariant; array index, indices; algorithm analysis; running time; upper bound; real-time;