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.