0
So let's see, what is
insertion sort's worst case time? OK?
Let us try to calculate the worst-case time of insertion sort. What is
insertion sort's worst case time?
Let's see This phrase is
often used to mean "Let's think together about this" or "Let me think some more about this."
13
So, now we getting into some sort of
funny issues... First of all, it's sort of... it depends on
the computer you're running on. Whose computer? right? you
know, is it, is it umm a big supercomputer or is it your wrist
watch
The question is not as obvious as it seems because the time depends on the computer you are running on. Whose computer [are we talking about]? Is it a big supercomputer or is it your wrist watch?
funny issues issues that are not profound but can be confusing. The word issue is sometimes used as a synonym of problem: "I have an issue with that."
sort of a qualifier, but it doesn't qualify anything here because the sentence is broken off and restarted
you know a very common filler, to give the speaker time to think. In today's American English, it is often preceded by like: "Like, you know, whose computer is it, anyway?"
36.667
OK, you know they have
different computational abilities OK.
And when we compare
algorithms, we compare them, typically, for relative speed,
They (supercomputer and wrist watch) have different computational abilities. When we compare algorithms, we compare them, typically, for relative speed.
abilities is usually said about people; capabilities about machines. He should have said capabilities.
relative speed speed that is relative to the computer on which the program that implements the algorithm is running. We do not compare speed across machines.The machine is the context relative to which we measure the speed of different algorithms.
50
OK? this is if you compared two
algorithms on the same machine. You could argue: "It
doesn't really matter what the machine is because I'll
just look at the relative speed."
We compare them [algorithms] for speed on the same machine. You could argue that this is all you need, and it doesn't matter that speed depends on the machine because we will just use relative speed to compare algorithms.
this is if you compared The word this refers to the new term and concept just introduced: comparison for relative speed.
look at a generic expression, here used to mean "use relative speed for comparing algorithms"
62.333
But of course I may also be
interested in absolute speed: Is one algorithm actually better
no matter what machine it's run on?
I may also be interested in absolute speed that is not relative to a specific machine. I would use it to answer the question: Is one algorithm actually better no matter what machine it's run on?
There is a hidden assumption in this sentence: relative speed comparison may give different results on different machines. This is not an obvious assumption, and the lecturer should have stated it explicitly, or else given a better reason for why absolute speed may be important.
73
pause, writing on the blackboard
78.333
And so this kind of
gets sort of con... confusing as to how I can talk about the
worst case time of an algorithm or a piece of software, while
not talking about hardware.
And so the question of running time becomes confusing because: how can I talk about the
worst case time of an algorithm or a piece of software, without talking about hardware [on which this piece of software is running]?
this kind of gets sort of confusing two fuzzy qualifiers in a row!
confusing as to how the conjunction as to is not often used.
88.333
OK? 'cos clearly if I run on a faster machine, my
algorithms are going to go faster.
Clearly, if I run my algorithms on a faster machine, they are going to go faster.
95
So this where you get the Big Idea of
... of umm algorithms, which is why Algorithms is such a huge
field, why it spawns companies like Google, like Akamai, like
Amazon OK,
This difficulty is the source of the Big Idea of Algorithm Analysis. It is because of this idea that Algorithm Analysis is such a big field in Computer Science. The results of this field helped create such companies as Google, Akamai and Amazon.
the Big Idea These words are in capitals because of the intonation of the lecturer. The phrase often means "the main point, the central most important idea."
116
why algorithmic
analysis has been such -- throughout the history of computing has
been such a huge success -- it's our ability to master and
to be able to take what's apparently a really messy
complicated situation and reduce it to being able to do some
mathematics, OK
[This big idea is] why algorithmic analysis has been such a huge success throughout the history of computing. This big idea gives us the ability to master a really messy complicated situation. It take a messy complicated problem and reduces it to a problem that we can study it mathematically. The problem is reduced to another problem that we can do mathematics about.
has been Present Perfect tense
be a success means the same as be successful
reduce a messy situation to being able to do some mathematics This sentence is not quite correct. It sounds as if the messy situation does some mathematics. See the paraphrase for alternative ways of saying this.
136.60000000000002
And that idea is called Asymptotic Analysis (pause, writes on
the blackboard)
That big idea is called Asymptotic Analysis.
144.333
and the basic
idea of asymptotic analysis is to ignore machine-dependent
constants and look - instead of at the actual running time -
look at the growth of the running time
The basic idea of asymptotic analysis is to ignore machine-dependant constants. The actual running time [of a specific algorithm on a specific input on a specific machine] is a constant. Instead of looking at that constant, we look at the growth of the running time.
look at again used in the sense of "consider, study."
instead of usually followed by a noun phrase, not prepositional phrase: instead of constants; instead of looking at constants
174.4000000000001
(pause, writes on the
blackboard) oops (pause)
oops Use this exclamation when you make a mistake and catch yourself.
188.333
ok
so we don't look at the actual running time, we look at the
growth, ok, so, let's see what we mean by that
So, we don't look at the actual running time, we look at the growth. Let's see what we mean by that.
199.667
So this is a huge idea - not a
hard... not a hard idea 'cos otherwise I wouldn't be
able to teach it in the first lecture but it's a huge idea,
we're going to spend a couple of lectures understanding the
implications of that, and we'll basically be doing it
throughout the term, and you
will
So this is a huge idea. It's not a hard idea. If it were a hard idea I wouldn't be able to teach it in the first lecture. However, it is a huge idea, and we are going to spend a couple of lectures trying to understand its implications. Basically, we will be using this idea throughout the term.
otherwise if thing are or were or had been different.
doing it Doing what? There are two possibilities: 1. understanding the implications; 2. "doing this idea" -- in other words, doing asymptotic analysis. The second meaning is more likely because of the next sentence.
219.865
- if you go on to be
practicing engineers, you'll be
doing it all the time.
If you go on to be practicing software engineers, you'll be doing it all the time.
doing it, again
224.86700000000005
Note that we're
going to adapt some notations that are going to help us, and in
particular we adapt asymptotic notation.
There are some notations for describing asymptotic analysis. These notations are helpful.
We are going to adapt those notations [for algorithm analysis]..
adapt Usually you adapt something for (doing) something else.
The intended meaning here is that asymptotic analysis is used in mathematics,
and some mathematical notations are adapted for algorithm analysis in computer science.
235.60000000000002
Ok, so most of you have
seen some kind of asymptotic notation - maybe a few of you
haven't but mostly you should have seen a little bit.
Most of you probably have seen some kind of asymptotic analysis. Most of you must have seen it.
Maybe a few of you haven't, but mostly you should have seen a little bit [of it].
X should have seen Y "It is likely that X saw Y at some time in the past."
X must have seen Y means the same thing but with stronger probability: "It is highly probable that X saw Y at some time in the past."
X should have seen Y may also mean: "X had an opportunity to see Y, but X didn't, and it was bad of X not to see Y."
246.33300000000006
The one we're going
to use in this class predominantly is Theta notation, ok, and
Theta notation is a pretty easy notation to master, because all
you do is just from a formula, you just drop low order terms
and ignore leading constants.
The notation we are going to use most often in this class is Theta notation. Theta notation is fairly easy to master. To find the Theta notation for a formula, you drop low-order terms and ignore leading constants.
the one we're going to use the notation we're going to use (one is a pronoun)
pretty easy quite easy, fairly easy, maybe not very easy but not difficult, either.
274.6
(pause) Ok, so for example, if I have a formula like 3n^3 +
90n^2 - 5n + 6046, I say: "Well, what's the... what
are... what low-order terms do I drop?" Well, n^3 is a
bigger term than n^2, so I'm gonna drop all these terms and
ignore the leading constant.
For example, consider the formula 3n^3 +
90n^2 - 5n + 6046. What low-order terms do I drop? n^ is a higher-order term than n^2, so I drop all these terms [after n^3]. I also ignore the leading constant [of the n^3 term].
for example, if I have... I say [to myself] a common way to introduce an example is by making it an episode, with "I" or "you" as the character.
309.06700000000006
So I say that's
Theta of n^3. That's pretty easy. OK.
So that's
asympto... that's Theta notation. Now, this is an
engineering way of manipulating Theta notation.
So I say that [the function described by] the formula is Theta of n^3. That's pretty easy. So, that's Theta notation. I should say that this is an engineering way of manipulating Theta notation.
Now this is an engineering way The word now is used to add a correction or qualification.
an engineering way as opposed to the formal mathematical way
324.53300000000013
There's actually a
mathematical definition for this which we're going to talk
about next time, ok, which is a definition in terms of sets of
functions, and you're gonna be responsible, in this class
-- this is both a math and an engineering, computer science
engineering class, so throughout the course you're gonna be
responsible both for mathematical rigor, as if it were a math
course, and engineering common sense, because it's an
engineering course, ok. So we're going to be doing both.
There is also a mathematical definition of Theta notation. We are going to talk about it in the next lecture. It is a definition in terms of sets of functions. This is both a math class and a computer science engineering class. In this class, you will be responsible both for mathematical rigor, as if it were a math course, and for engineering common sense, because it's an engineering course. We will be doing both.
responsible for In the context of a course study, to be responsible for some material means that your grade will depend on how well you know that material. Most likely, it will be on a test or an exam.
355.6000000000001
Ok, so this is the
engineering way of understanding what you do, so you're
responsible for being able to do these manipulations;
you're also going to be responsible for understanding the
mathematical definition of Theta notation, and of its related O
notation and Omega notation, OK?
To repeat: this [example] is the engineering way of understanding how you do Theta notation. It is a way of manipulating a formula. You are responsible for being able to do such manipulations. You are also going to be responsible for understanding the mathematical definition of Theta notation. There are two more notations called Big-O and Omega notations. They are related to Theta notation. You are responsible for understanding these two notations also.
and of its related O notation and the O notation that is related to it.
373.4000000000001
So, if I take a look, as
n approaches infinity, a Theta(n^2) algorithm always beats,
eventually, a Theta(n^3) algorithm.
[Returning to the discussion of Theta notation] If we take a look [at the asymptotic behavior] as n approaches infinity, a Theta(n^2) algorithm will always perform better, eventually, than a Theta(n^3) algorithm.
take a look Just as
look at before, this means "consider, analyze, investigate"
beat come out better in a competition
398.5330000000001
As n gets bigger,
doesn't matter what these other terms were, if I were
describing the absolute precise behavior in terms of a formula,
ok, if I had a Theta(n^2) algorithm it would always be faster
for sufficiently large n than a Theta(n^3) algorithm.
If I were describing the absolute precise behavior of the function in terms of its formula, I would have all the low-order terms were here.As n gets bigger, it doesn't matter what those low-order terms are. Only the highest-order n^3 term matters. If I had a Theta(n^2) algorithm it would always be faster
for sufficiently large n than a Theta(n^3) algorithm.
If I were describing This is a contrary-to-fact condition. Note that the form were is used with singular nouns and pronouns.
absolute precise absolutely precise would be more grammatical
If I had a Theta(n^2) algorithm another contrary-to-fact condition.
418.6670000000001
Wouldn't matter what
those low-order terms were. Wouldn't matter what the
leading constant was. OK? This one will always be faster - even
if you ran the Theta(n^2 algorithm on a slow computer, and a
Theta(n^3 algorithm on a fast computer.
[In comparing Theta(n^2) and Theta(n^3)], it wouldn't matter what
those low-order terms were. It wouldn't matter what the
leading constant was. The Theta(n^2) one will always be faster -- even
if you ran the Theta(n^2 algorithm on a slow computer, and a
Theta(n^3 algorithm on a fast computer.
Wouldn't matter The pronoun it is sometimes dropped in informal speech. The form
would is used because we are continuing the contrary-to-fact condition of the preceding sentence ("if I had...").
even if you ran another contrary-to-fact condition
440.93300000000016
So the great thing
about asymptotic notations is it satisfies our issue of being
able to compare both relative and absolute speed
We raised an issue or a problem: how do we compare algorithms for absolute speed . The great thing about asymptotic notation is that it resolves that issue. We can use it to compare absolute speed of algorithms,
satisfies our issue the verb resolve is more commonly used with the noun issue. On Feb. 4, 2007, "satisfies the issue" had 84 hits in Google, while "resolves the issue" had 139000 hits.
450.867
ok, because we're able to do
this no matter what the computer, no matter what the platform.
because we can do asymptotic analysis no matter what the computer, no matter what the platform.
458.667
So on different platforms we
may get different constants here, machine-dependent constant
for the actual running time, but if I look at the growth as the
size of input gets larger, the asymptotics, generally,
won't change.
We may get different constants on different platforms. The constants of the actual running time are machine dependant. However, if we look at the growth [of running time] as the size of the input gets larger, the asymptotic behavior of this growth function usually will not change.
platform specific computer hardware or a specific combination of hardware and operating system ("the Linux platform").
generally a qualifier indicating that there are rare exceptions to this statement.
Grammar topics:
- Spoken language:
- fuzzy qualifiers (kind of, sort of - pronounced kinda, sorta)
- Irregular plural of nouns
index - indices; analysis - analyses
- Contrary-to-fact conditionals, with otherwise; the use of would
ex6
Expressions:
look at (an abstract thing); the same thing; we're done (are you done?); take (time duration);
Vocabulary:
otherwise
CS terminology :
running time;
