0:00

[MUSIC]

Â So in the last video, we talked about how we're going to measure performance,

Â based on counting operations.

Â So we're going to count the number of operations that are performed

Â every time we execute code.

Â So, let's practice how to do that.

Â By the end of this video, you'll be able to count the operations

Â when you look at a particular code snippet.

Â And think about what happens when we run it for a given input.

Â All right, so the code that we're going to focus on is going to solve the answer,

Â answer the question of looking for a particular letter in a word.

Â And we'd like to think about how long that takes.

Â So, for example, we're going to look at the word or two words, but it's a single

Â string, San Diego, and we're going to search for the letter, lowercase a.

Â Now in order to do that, Christine showed you a method in the previous lesson where

Â we have the method hasLetter, which has input both the string,

Â which is the word that we're looking in.

Â And the letter that we're looking for, so that's a character.

Â So we have those two inputs, and then what we're going to return is a Boolean

Â which says true if we found the letter in the word and false if we didn't.

Â Okay, so

Â thinking about this algorithm, what we're really doing is a linear search.

Â We're gonna go through the entire string, which remember, is an array of characters,

Â and we're going to start at the beginning.

Â And one by one, character by character, we're going to compare

Â the current character to the letter that we're looking for.

Â So we start at the beginning with our index being at 0 and

Â then we keep checking whether the character at that index 0,

Â is the same as the letter that we're looking for, which was input by the user.

Â So we have our example word San Diego and we're looking for the letter a, remember.

Â Okay, so we start by initializing our loop counter i, and

Â that counts as a single operation.

Â And now we check that our loop counter is less than the bound, and so

Â we're comparing 0, the current value of i, to the word length, which is 9.

Â And what we need to do now is say, okay, yes, that's correct,

Â 0 is less than 9, and so we keep on going.

Â But we have to increment the number of operations that we've done,

Â because that test is an operation.

Â All right, so now we've gone into the body of the for loop and

Â inside the body of the for loop we have an if statement, a conditional branch.

Â And what we're checking here is whether the letter at position 0,

Â which was our current value of i, is the letter that we're looking for.

Â But notice that even making that check, testing that condition, is an operation.

Â And so we have to increment our operation count once more so, so

Â far three operations.

Â 2:39

In this case, the current character is a capital S that's not the same as little a.

Â And so we don't execute the body of the if branch at this point,

Â we go up to the top of the for loop.

Â We increment the counter i, oh, incrementing, that's another operation.

Â And now we check that our current value of the counter,

Â which is 1, is less than the word length.

Â It is, and so we go back inside the for loop.

Â But that means that we have to increment our operation count

Â because we did another check.

Â Okay, so we're now back inside the if and

Â we're checking whether the current character, little a,

Â matches the letter that we're looking for which is little a, all right?

Â So this check evaluates to true, but before we go ahead and

Â follow the logic, we remember that we have to increment our operation count.

Â And now that we've decided that we have to go inside the if branch, we go in and

Â we return true.

Â Returning is an operation, and so our total number of operations is 7.

Â Okay, so hopefully that trace through gives you an indication

Â that we have to count each time that we execute a statement.

Â Or that we evaluate a conditional branch, or

Â a check, something that evaluates to a Boolean.

Â 4:19

So in those quizzes hopefully you got a sense of just how many

Â variables there are for

Â deciding how many operations get executed when we run a method on particular inputs.

Â And so let's recap what you saw in those quizzes and let's think about what happens

Â when we search for the letter x, still in that same word San Diego.

Â So we're still looking at the hasLetter method and

Â now we're thinking about just looking for a different character.

Â So when we think about counting operations, I know that I think about

Â groaning because I don't wanna do that same line by line counting each one again.

Â That was kind of painful but I'd like to find a shortcut.

Â So let's think instead of grouping a whole bunch of instructions,

Â a whole bunch of operations into maybe something higher level, that then I can

Â think about how that higher level construct repeats over and over.

Â So let's think about what happens as we go through a single iteration of the for

Â loop, what that body of the for loop is going to contribute to my operation count.

Â And so, in a single iteration, what I need to do is,

Â well I need to test whether my current loop counter is less than the bound.

Â I need to, in that case, perform the contents of the body of the for loop.

Â And then I'm going to need to increment my loop counter.

Â Okay, so each of those contributes one instruction,

Â in this particular case, to the operation count all in all.

Â And this is, of course, assuming that in this current iteration of the for

Â loop I haven't found the character that I'm looking for,

Â because that would kick us out of the for loop.

Â And so let's just think about what's happening in an iteration, somewhere in

Â the middle of my algorithm, somewhere in the middle of the execution of the code.

Â And so in that case, each iteration takes 3 operations.

Â And so if we think back to looking for 'a',

Â then we only really did 2 iterations of the for loop.

Â We went through an iteration when our loop counter was at the 0, so

Â we were comparing a to capital S, and

Â then we had an iteration with our loop counter at position 1.

Â And so then we were comparing a to a, and then we broke out of the for loop and

Â were happy.

Â Okay, so, when we had just the 2 iterations, we got 7 operations.

Â And so now let's think about the how many iterations of the loop are there,

Â when we're looking for the letter 'x'.

Â Okay, so thinking back to the algorithm,

Â we're going from the beginning to the very end of the word San Diego.

Â And so we're going to be looking through every single position of the string, and

Â that means that there's going to be an iteration of the for

Â loop for each of the positions in the string.

Â And there are 9 such positions because this is a length 9 word.

Â Okay, now we can go ahead and do the calculations for

Â the number of operations based on the 9 iterations.

Â We see that there are going to be 29 operations.

Â And now you might stop and say, whoa, hold on,

Â I know my arithmetic, 9 times 3 is not 29, it's 27!

Â Think about what happens at the very beginning, when we initialized

Â the variable i, and at the very end, when we break out of the loop.

Â And so, there's going to be some niggly little counts at the very beginning and

Â the end that aren't exactly the same,

Â it's just doing 3 times the number of iterations.

Â 7:45

But in all of this, we're kinda sweeping under the rug,

Â this question of what counts as an operation?

Â What does it mean to have an operation?

Â And so, when we first started out,

Â I suggested that every time we execute a statement, that's an operation.

Â And every time we evaluate a conditional statement and ask for

Â the Boolean value of that conditional statement, then that's an operation.

Â But you might ask, well how did you know?

Â How did you know that when we returned to something that's an operation?

Â What about other possibilities, or can I group operations?

Â What if I have a single line that's both a variable declaration and

Â an assignment, is that one operation or two?

Â Who knows?

Â Well so that's a really good question and

Â it goes to the heart of what we wanna do when we're analyzing performance.

Â What we'd like to do is not worry about this question,

Â what we'd like to do is only worry about

Â the pieces of the algorithm that we can control as algorithm designers.

Â And not so

Â much about the implementation of how a single line of Java code gets executed.

Â And so a way to think about an operation, is a basic unit

Â of execution that doesn't change as the input changes.

Â So when we have a single line of code that is both a declaration and an assignment,

Â then what we're doing in that single line of code doesn't depend on the input.

Â How long it takes us to do that doesn't really depend on the input and so

Â we can count that as a single operation.

Â So a basic operation is something that doesn't depend on the size of the input,

Â it doesn't depend on what happens with the input.

Â And so what we'd like to do is not worry so

Â much about whether we count such a declaration plus assignment as two

Â instructions or one, and just think of it as a single operation.

Â And the tools that we'll be developing in the next video will help us do even

Â more of that kind of abstraction, where we're less worried about counting

Â every single operation and every single line.

Â And rather look at the whole scale performance of the algorithm,

Â specifically as the input grows and the input size gets really, really big.

Â