0:14

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.

Â 2:02

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.

Â 2:15

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.

Â 2:40

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.

Â 4:15

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.

Â 4:34

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.

Â 5:26

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.

Â 5:47

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.

Â 6:02

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.

Â 6:43

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.

Â 7:29

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.

Â 8:48

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.

Â 9:26

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.

Â 10:04

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.

Â 10:30

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.

Â 11:31

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.

Â 12:06

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.

Â 12:31

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.

Â 13:39

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.

Â