[MUSIC] Welcome back. In this video lecture we're going to talk about understanding the efficiency of the Python programs that you've built. When you click Run, Python executes your programs and takes your input and builds answers. Right now that's probably somewhat of a mystery to you. We're not going to get really specific here. We're just going to kind of learn to build a ballpark estimate of how long it takes Python to compute the answers from the inputs that you give it. Ideally we'd like to develop some understanding where if we look at the inputs, we can roughly predict how long your program will take to run, in terms of some formula of the size of those inputs. We're not going to get super precise in principles of computing. In algorithmic thinking, we'll actually get much more precise in terms of compute determining the efficiency of the programs that you're building. In this one, we're just going to get a ballpark estimate. I'm going to start by kind of looking at a, at a of humorously example of learning how to count, to estimate the size of something. Okay, let's start off by considering this giant pile of cash. This is the money that Scott and I have made from teaching an Introduction to Interactive Programming in Python. Okay, that's not really true. We can put in a good picture of this with empty room with few dusty $20 bills sitting on the floor. This is actually a giant pile of cash seized from a Mexican drug lord. It was probably the, the inspiration for the giant pile of cash that Walter White had in Breaking Bad. So the first thing that I, thought when I actually saw this pile of cash was, how much money is that? That's a heck of a lot of money. So, when we talk about counting and trying to estimate things. I'm going to show you an example here of how we can actually estimate how much money is here surprising accurately. The first thing we need to figure out is we have all these little packets of money here. So those are hundred dollar bills. And it turns out they're strapped together in bundles of a hundred. So we have $10,000 in each one of these little packets. Okay. Well, how many packets are there? Looks like there's a lot of them. So, we could just observe this as kind of a big giant brick. So we can estimate the number of packets by computing kind of the width times the height times the depth. So let's do that so there's kind of like five, ten, 15, 20, 25, 30, 35, 40, 45, maybe 50 packets wide. Maybe let's see, five, ten, 15, 20, 25, 30 maybe, 30 packets high. Then five, ten, maybe 15 packets deep. So we can actually just go out there and let's just go to CodeSkulptor and just print out what that is. So it's 10,000 times 50, times 30, times 15. Let's run that. Well the answer is 225 million. So I actually looked up how much money was here and it turns out there was actually $209 million here. So what we kind of this example points out is you can actually do a surprisingly good job of, of estimating something that you think you have no chance at it. If you just follow a few simple principles. So what we're going to do here is I'm going to talk about trying to estimate the number of statements that are executed when you hit Run in your Python program. So let's get down to business. [BLANK_AUDIO] So let's look at the problem of trying to estimate the number of statements that are executed in your Python IDE whenever you click the Run button. So I've got kind of a sample program here. And it's sitting here in CodeSkulptor. In fact, we're sitting inside Viz mode. So I want to show you what I mean when I'm talking about trying to kind of measure the, the requirements of your program. So if I click Run here what happens is Code Skulptor went through and executed this program, and Viz mode made a trace that recorded each statement that was executed when we ran the program. So if you've used the, the Viz mode before, we start off, we're getting ready to ex, getting ready to execute statement seven, we click, we go forward to eight, to nine, we go to twelve. We skip into thirteen, we skip fourteen. Then we go down to this loop. And we click the loop, and we actually execute the loop ten times. So notice what happens here is when we clicked Run, CodeSkulptor went through and executed this Python programming statement one statement at a time. Now the important thing to note here is this is somehow doesn't really exactly capture how long it takes to run the program because, it depends on things like how fast your computer is. How fast your browser actually executes the JavaScript that your Python is translated into. How skillful the people that wrote Skulpt, the engine for CodeSkulptor, were. So we're only trying to really kind of figure out kind of what we can control, which is kind of, kind of how our Python program is executed. And for now, we're going to just consider it a statement level. That kind of gives us a ballpark estimate that will allow us to actually form some thoughts about whether we have a good or bad program. Okay, so now I can be more precise about what we really like to do. What I want to develop is kind of a process that lets me to look at the structure of my program, and derive a formula that estimates the number of statements that will execute based on the structure of the program, and the values that we feed to that program. So, for this simple example here, we can actually make some headway. For straight line code it's very easy to estimate the number of statements we execute. Just go bam, bam, bam right through here, we do three prints. For conditionals we can kind of estimate how many statements we're going to execute inside a conditional. We can just kind of take the maximum of the statements inside each of the two branches, or we can add them, remember we're going for a ballpark estimate here. The critical thing is for things like straight line coding conditionals, kind of the size of your program kind of gives you about how many statements you will have to execute. However, if we get down to this loop, things get a little trickier. Okay, we are getting execute this loop, and we jump in there and we print one test, we print two test, we print three test. We bang along here and we actually end up executing this loop ten times, okay. So, could we make that trace longer? Will we make the number of steps, statements we execute longer? Well we could change this to 100. And we could fire it up, and, wow. We have 100 prints here. And our trace is probably like more than 200 statements long. So, somehow it's not just the size of the program it's also some of the values that we give in to the program. And in fact loops are kind of the, the first place we're going to see some trickiness and try to understand kind of, how much computation is done when you run your program. So what I want to do is we're going to actually look at kind of analyzing kind of the, how many statements are executed when you run a loop. And this will lead into some kind of simple mathematics that you will need to know to help do the analysis we're going to need to do in this class. Okay, let's look at some examples involving loops. So, in the second half of the file that I've given you, we have three functions whose bodies are either loops or pairs of loops. And, the reason I have written these as functions is because I want to emphasize the point that the number of statements that are executed whenever we evaluate these loops, will depend on the input values that we give those functions. So we're trying to emphasize input values, give us some way to estimate, the running time of our program. That's what we're going to be shooting for as we move forward. So let's look at this first function here, test1. Its body simply consists of a, of a loop, that takes the input value and prints out test1 that number of times. So we see here, we gave it four. It printed out test1 four times. I could change this to ten and guess what? It's going to print out test1 ten times. So looking at this really simple loop, we can very easily estimate the number of statements we're going to execute. The number of times we're going to print out test1. By just giving a little simple math here, we give it n, it's going to print out test1 n times. The number of statements it's going to execute, well it's kind of twice that, maybe we execute to four, then we execute to print. But really, the critical thing is it's growing linearly as this parameter here. Alright, let's look at a second example. So the second example, test2, has a pair of nested loops. In this one we give it a value, and this index1 ranges from there, from zero to that value. The interloop then range, ranges from zero to index1 plus 1. So for example if we give this the value one, it will print out test2 once. If we give it two, it will print out test2 three times. If we give it three, it print out test2 six times. If we give it 4, it'll print out test2 ten times. So, what's happening here? Well, when we run test2, this inner loop is being executed one time, then two times, then three times, then four times. So, if we add up all the executions for all four times to the outer loop, it's 1 plus 2 plus 3 plus 4, or ten. So what you can see here is, we've built a sum that helps us understand how many times this pair of nested loops is executed. So we're going to do later in the lectures is I'm going to walk through some of the simple sums that you'll need to do, need to know to do analysis just like I've shown you. Okay, let's look at this last example. So in the last example, we're, outer loop is iterating from, again, from zero to the input value. But the inner loop is doing some exponential of this index. So for example, when we start out, let's run this on one. We can see is test3 actually was printed once. That's because the initial value here is going to be zero. We take 2 to the 0, that's 1, so we print this out exactly once. Change this to two, and see if we can figure out what's going on. So we change it to two, and we see test3 three times. That's because this inner loop executes once, 2 to the 0, then a second iteration, it executes two times, 2 to the first. So let's see. If we change this to three, I'm going to guess that it's going to execute seven times, it's going to be 1 plus 2 plus 4. So, there it is, 7 times. So, what this is, is actually going to be a sum of numbers that are growing exponentially. So again, we need to look at some more sums to understand how those things grow. So, what I want to do now is that we're going to actually go over to a class web page where I kind of walk you through the basic math of doing arithmetic sums. All right, let's finish off lecture by looking at some common arithmetic sums. So I've built a class page that contains a kind of small set of notes that you can review and kind of parse to understand the basics of the math you will need here. The most critical thing is that you need to understand the common notation that mathematicians use for writing a sum. If we have a sequence of numbers that are indexed by some index i, maybe a0, a1, a2, and so forth, use a subscript for that, we can express the sum of all those numbers by using this sigma here. Where kind of the subscript says the index from sum lower bound to sum upper bound. So here zero is the lower bound for the sum, n is upper bound for the sum. As opposed to Python we always include both the lower bound and the upper bound inside the sum. So here are some examples of some common sums that you might find in this class. This kind of corresponds to the loop test1 here. We do a constant amount of work inside each iteration of the loop. And we have n plus 1 iterations of the loop. Well, what comes out is we have n plus 1, so the sum of numbers 1 plus 1 plus 1 plus 1, n plus 1 times is exactly n plus 1. Here's a second one. This might come up if you had a pair of nested loops. In this particular case we're taking the number n and we're adding it together n plus 1 times. So it's no surprise the answer is n plus 1 times n. Notice this is a quadratic expression and this is a quadratic polynomial and it, so. Much of the time, whenever we're trying to estimate the running time of a program, we'll actually just worry about mainly kind of a very rough expression of what the, kind of the, the formula is for that running time. Look at things like, is it linear, is it quadratic, is it exponential. So we're not going to worry the, kind of the small details too much. Here's another example. This is the example for Test2. In this particular case, we are adding up the numbers 1, plus 2, it's actually 0, plus 1, plus 2, plus 3, all the way up to n. So this is called a triangular sum, and the formula is one half n plus 1 times n. The critical thing again is quadratic and n. The one half again is not as important. The main thing is, it's quadratic in n. So for example if we double n, the fact that it's quadratic means that the sum would actually grow by a factor of four. Here's another example. This is called a geometric sum down here. We're adding up 1 plus 2 plus 4 plus 8 plus 16. It turns out there's a very simple formula here. 1 plus 2 plus 4 plus 8 plus 16 is exactly 32 minus 1. There's a few more formulas down here. There's formulas for what's called a harmonic series. You'll actually use that in the homework so my suggestion is you read over this fairly quick, fairly carefully. You don't have to remember the solutions for the sums, you just have to know where they are so you can look them up. Because you will be applying them every now and then inside the class. Okay, I'll see you next lecture.
