0:03

[MUSIC] So in the last video,

Â we got all tied up in questions of what an operation is.

Â How do we count every single last operation

Â when we execute a piece of code on a given input?

Â And now, what we'd like to do is just clean away all that clutter,

Â clean away all that mess, and talk about asymptotic analysis.

Â So by the end of this video, you'll be able to explain why asymptotic analysis is

Â so useful, and then start calculating the big O class,

Â which is that indicator of asymptotics of particular code snippets.

Â So we've already got some of that motivation based on the pain that we went

Â through in the previous video.

Â What we'd like to do is not have to worry about things that we can't control.

Â So we'd like to let go some of the details, and

Â think about the big picture of how our algorithm or our problem solving strategy

Â behaves, in particular, relative to big data and big inputs.

Â So we're going to think about putting away the details of the initialization time of

Â the execution.

Â So if there are certain things that we need to do at the beginning,

Â some variables we need to declare.

Â Or some tidying up stuff that we need to do at the beginning of our code.

Â We don't want to have to worry about that.

Â We also want to not have to worry about implementing specific operations.

Â How do those happen?

Â Especially if they don't have anything to do with how our input size

Â determines the runtime.

Â We don't need to think about them at all.

Â And so what we'd like to do is come up with a principled theoretical way of

Â analyzing our algorithm.

Â But something that's a little bit more sophisticated than counting each

Â instruction and that has this wider purpose of not having to

Â worry about the nitty picky details of the specific operations and

Â things that have to do with initialization time or small inputs for our algorithm.

Â Okay, so our focus is going to be on how the performance scales,

Â how our algorithm runs as we give it bigger and bigger inputs.

Â So, that motivating question that we talked about earlier is,

Â if our input is twice as big, how many more operations do we need in general?

Â Okay, and so, that's going to be motivating us throughout.

Â So let's start to think about some specific code snippets.

Â And these are, you'll recognize them,

Â taken from that hasLetter method that we were thinking about before.

Â So let's think about this, just the if branch that we have right over here.

Â And think about how it behaves, with respect to word.

Â So our input here is that string word.

Â And when we're thinking about performance,

Â we're thinking about it relative to the input size.

Â So if we have a string, then the size of that string is the length,

Â the number of characters in that string.

Â And you'll notice that whenever we talk about asymptotic analysis,

Â when we talk about inputs, we usually use the letter n

Â to represent the size of the inputs that we're given.

Â So as we work through these examples, whenever you see a little n pop up,

Â that's our representation of the size of the input, okay.

Â So for this particular piece of code, when the word is our input, and

Â so its size is n, the number of characters in the string.

Â What we'd like to think about is how long does it take to execute this if branch.

Â And so, in our previous model, we counted operations.

Â But right now what we'd like to do is maybe not have to count all

Â the operations, but think about how does the number of operations change

Â as the word gets bigger or smaller, as we have different inputs?

Â And if we think about what we're doing in this if branch, we're doing

Â one comparison, comparing a particular character with another character, and

Â then either doing zero operations, or one operation.

Â Okay, so this if branch is either going to have one operation associated with it,

Â just the comparison, or two operations associated with it, the comparison and

Â the return statement.

Â And notice that all of that calculation,

Â what we just did, didn't depend on the size of the word at all.

Â We had to think about two cases based on the particular character, but

Â nothing to do with the size of the input.

Â And so the number of operations is constant if all we're thinking about is

Â the size of the input.

Â Okay, so this is an example of a constant time code snippet.

Â So let's look at another code snippet, and in this code snippet,

Â what we're doing really is just counting the number of characters in our string.

Â And so let's think about how the runtime of this code snippet changes

Â as our input string grows and grows and grows.

Â And so what we're doing over is here is we're taking the input, which is still

Â the string word, and notice that here we're still going to call the size n.

Â And again it's the number of characters in the word.

Â But now the size is starting to play a role in the execution of the code.

Â Because what we're doing here is we're stepping through, in this for

Â loop, through each character in the string, and so

Â the number of operations is going to grow as the string grows.

Â And how is it going to grow?

Â For every new character in the string,

Â we're going to have to go through one more iteration of the for loop.

Â Because the length is going to be just one bigger.

Â So every time we add one character to our input, one additional

Â character to our string, we're adding one more iteration to the for loop.

Â And in that for loop, well, we're just doing one instruction.

Â So, every new character in our string adds one more instruction overall.

Â And this relationship, well, if we go through that calculation,

Â we have one instruction for the initial variable, declaration and assignment.

Â And then, n times through this loop, we're going to check

Â our loop counter, increment the count, and then add one to our loop counter.

Â And that's gonna happen n times.

Â So overall, the run time of this piece of code is going to be one for

Â that initial piece, and then within that body of the for loop,

Â we're going to have one for declaring the loop counter i.

Â And then for each iteration of the for loop,

Â we're going to have three instructions.

Â And then we're going to have one additional instruction at the very end,

Â when we've incremented the i too many times and it's bigger than

Â the length of the string, and that's gonna kick us out of the for loop.

Â Okay, so overall the number of instructions that we execute is 3n + 3,

Â putting all of those pieces together.

Â Notice that that's a linear function of n.

Â Okay so thinking back to calculus and definitions of linear functions,

Â when we have an input being mapped to some constant times that input,

Â maybe plus another constant, that's a linear function.

Â Okay, so the run time in terms of the number of operations of this piece of code

Â is linear, so it's linear time.

Â So we've seen a code snippet that was constant time,

Â relative to the size of its input.

Â And now we've seen another code snippet that's linear time,

Â relative to the size of its input.

Â And now what we'd like to do, is phrase this more broadly,

Â in the sense of big O classes.

Â And so, when we say that one function is big O of another function, what we

Â mean by that is that those two functions grow in the same way as their input grows.

Â Because what we'd like to do in this big O notation is say I don't wanna

Â care about the constants I don't wanna have to keep track of the plus one here,

Â and the plus three there.

Â What I like to think about is the rate of growth of the functions.

Â And so when we looked at that second function over there,

Â the one that had the linear time, we don't want to focus on the fact that it was

Â three n plus three, but rather that notion of it being a linear function of n.

Â That it grew just a little bit with every time that we increased the input

Â by a little bit.

Â Okay, and so this big O notation is going to be our way of capturing

Â the rate of growth of two functions, and so we say that

Â two functions are in the same big O class if they have the same rate of growth.

Â Okay, now disclaimer, in industry and

Â in practice, this is the way that most people use big O.

Â The way I just said it.

Â The big O class means that the two functions grow in the same way.

Â Now, if you look at the text books, if you Google asymptotics,

Â you'll notice that there are a lot of different ways of measuring asymptotics.

Â So, there's big O, which we'll be talking about.

Â There's also something called big theta, big omega,

Â little o, all of these different kinds of classes.

Â And they're going to represent a finer-grained analysis of the asymptotics.

Â Sometimes we just care about lower bounds or

Â upper bounds, and that's going to be useful as well.

Â But what we're going to do in this course and in our analysis,

Â is focus on the big O, and we're going to use that as shorthand for the tight bound.

Â Now, that's not exactly how it's used In the formal definition, but

Â for us big O is gonna be the tightest description

Â of the asymptotics of the function that we can come up with.

Â