[MUSIC] Welcome to class. In the last video, we began the process of trying to understand the running time of your program as a function of the size of its input. In this previous video, we built a mathematical model for how many types of particular statement was executed in the program that involved creating an arithmetic sum that depended on the size of the input. In this video, we're going to take a different approach. We're simply going to go through and add a counter at a particular location in your program and then run that program on inputs of various sizes. We'll then collect the number of times that counter is executed for each particular input size, collected in the list. We can then plot the resulting list and look at the number of times that counter is executed versus the size of the input. We'll finish off the lecture by talking a little bit about how to massage the plot, so that we can tell whether the resulting graph is the plot of a linear function, or a quadratic function, or any kind of polynomials function. Okay, let's get to it. Okay, let's consider this example code that I've loaded here in CodeSkulptor. So if you look on the screen here I have three functions that I've defined, mystery1, mystery2, mystery3. I've used code folding to hide the body of these functions. When you load them in, you can either look at the body or you can fold it up and hide it yourself. But the problem that we're going to try to attack here is to understand the running time, kind of the length of the execution trays, each of these mystery functions, has a function of input_val. So as I change input_val, each of these functions takes longer to execute. We'd kind of like to know, kind of, what's the relationship between input value, and the execution time. So, to do that, what I've done is I've built on global counter, I'm sorry Scott. And I've essentially inserted in the execution of each mystery function, a statement that increments the value of this counter each time we do whatever we want to analyze. In this case, we have a collection of loops, so every time we execute the body of the innermost loop, we increment the counter by one. So then I built this plotting function down here that I can pass in a plot size, kind of the range for the input values, the function we're going to plot, mystery1, mystery2, mystery3, and then a plot type we'll talk about in a second. So, now notice what happens here. It's very simple. We just start out with a plot that's an empty list and we choose var, various values for the input size. We run the plotting function, and then we grab the value, at the input value, grab the input value and the counter, and append it to the end of the plot. So, the result of this is a list of points, and kind of a two-dimensional space, the input value versus the counter size. So we like to do now is actually figure out how to make sense of that data cell. So we're going to talk about plotting. [SOUND] Okay, let's talk about how to plot data. So the basic idea is we've created this list of points, and we'd now like to make a picture of it. So in Python, the standard method of doing this is choose a plotting package. Now we're at python.org here there's literally, if you look at this, there's dozens of various packages available for doing plotting. This is a little bit like what we face when we use simple gooey versus TKinter, Pygame, or wxPython [INAUDIBLE]. There's lots of different packages for doing gooies. There's lots of different packages for doing plotting. If you're working on idle and you want to stay, basically, solely on the desktop, pick one of these packages. Read over it, figure out how to use it, it shouldn't be too hard, and you can plot your data. We provided a custom plotting package inside CodeSkulptor. It's extremely simple, it's called simple plot, it basically allows you to make line plots, it's there for your convenience. I'm going to use it in the example here, because it's easy to do and works very nicely inside CodeSkulptor. You're not required to use this though. But the critical thing to understand here is the philosophy of Python. When you want to pick up and learn how to do things, you're going to have to understand how packages written by other people work. That's part of the survival skills inside Python. So, when you here this thing says, well why don't you teach me the right way to plot or the right way to build a GUI. In Python, there are many different ways to do this and so the ability to move back and forth between packages is a key skill that you're going to have to hone in this class. All right, so let's talk a little bit about how simple plot works. You can find it in the docs here. Under the Documentation, you click on Graphics Modules, scroll down. There's really only two operations you could do in simple plot. You can make a live plot or you can make a bar plot. The syntax is here. At this point, you should be able to basically read the docs and figure out how to do it. I'll go back and show you an example inside my code here in just a second. [SOUND] Okay, let's do some plotting. So, we return back to our example code, here you see my three mystery functions. Here's my plotting function that actually builds the plot. And down here, what I've done is I've called that function, build_plot, three times, with a plot size of 40 each of those. I passed in the names of the three mystery functions. I'm going to do a standard plot for now. And so here's a critical thing, I've called simpleplot.plot_lines, and, one thing that really we have to pay attention to here is that we can give it multiple sets of data to plot. So, we give it a list with the three plots here. So, this is a list. Each of these entries is a list of points. So, when I click Run, what pops up is a window with my three pot, three plots. So, this is the plot of the first function. This is the plot of the second function. This is the plot of the third function. So, just by looking at this, we can kind of deduce some simple properties of these functions. The first function looks like it's a linear. So, what that really means is that if we look at the input value, the number of steps we're taking this, the, the value of the counter is going to be linear function of that input value. So particular, if we double the size of the input value, the number of, the value of the counter number steps in there would actually double. The second and third functions, it's a little more unclear. It looks like they might be polynomial functions. Maybe it's quadratic and this one is cubic. It's important to know whether a function is polynomial versus, say, exponential. For example, if a, if a function is quadratic and we double it, the, the running time just goes up by a factor of four. If it's cubic, the running time goes up by a factor of eight. But if the function is exponential and we double the size of the input, we square the running time and just goes crazy. So in fact, exponential functions we [INAUDIBLE], we run them for a large input in most cases. So what we're going to next is let's talk a little math and I'll show you kind of a trick to ans, answer the question about whether these functions are actually polynomial or not, we're going to use logarithms. [SOUND] Hi. During the course of this class, you'll work with two functions occasionally. Let's go over those functions very quickly here. You may want to do take logarithms and you may do exponentials. So an exponential, you've probably seen in high school math. You take some number and you raise it to a particular power. We're going to actually use the natural exponential function here fairly frequently. It sometimes denoted exp of n. In it all, it really is as Euler's constant which is 2.718 raised to the nth power. Euler's constant is a magic number. You can look at the Wikipedia page if you want to understand where it comes from but for now just think of it as a constant between two and three. The second function we're going to work is logarithm we're going to use the natural logarithm again fairly frequently. So, the natural log of the number n, we just simply take it to base e, it's the, it's the power you have to raise e to get n. These functions are actually inverses of each other. Which means, if we take the exponential and we take the log, we get back the original input or we take the log and then take the exponential, we get back the original input. Notice that in some cases, you want to work with the different base, you may want to do base 2 or base 10. The typical notation you'll see here is log with the subscript that corresponds to the base. Probably the most important thing to understand about exponentials and logarithms are they kind of obey the following two rules down here. That if you have something to the n plus m power, it's really just the product of something to the nth power times something to the mth power. 'Kay, essentially you may remember this from 8th grade algebra. You add exponents. With logarithms, it's kind of the complimentary thing. If you have the logarithm of the product of two numbers, it's simply the sum of the logs of each of the numbers. 'Kay, this is a very useful piece of information here. So next, I'm going to show you how to go through and actually use this to do log/log plotting. [SOUND] So we've taken our mystery functions, we've built a plot of them, and now we're trying to understand the behavior of the, kind of the running time. The value of this counter is a function of this imput value. So kind of a metric for whether you've got a reasonably behaving function is to ask is the running time a polynomial of the input value. So we kind of like to ask, okay, x is the input value, is the running time y some polynomial function of it. So it turns out we can use logarithms to help kind of understand and answer that question. I mean here's the trick, if y is equal to a times x to the n. If we take the log of both sides, we get log of y is equal to log of a, x to the n. Remember the product rule for logarithms says we can break this apart, all right? This is log of a plus n, times log of x. So if our data points, actually satisfy this relation, y equals a to the e, why equals a, times x to the n. The data points should have the property that the log of the y value should be a linear function of a log of the x value. So in fact, this is a strategy we can use when we're actually plotting our data to figure out if our data lies on a polynomial curve. We'll take the log of the x and we'll plot it versus the log of the y. And if that's a straight line, then guess what? The data lies on a polynomial function. And in fact, it's even better. If we look a the slope of that line, the slope of that line is exactly n. It's the degree of the polynomial. So in fact, this is a trick behind something that you'll see in lots plotting packages, called log/log plotting. It's hidden a little bit, because what they'll do is they'll take the labels on the axis. Instead of spacing them evenly, they'll space them geometrically. You might see this where you'll see the label be 1, 10, 100, 1,000, 10,000, 100,000, 1 million, and they're all equally spaced. What they're doing is they're basically doing this log trick here. So, what they're doing is they are plotting the data point by taking the log of each of the values. That has the advantage if the data grows really quickly, you can still make some sense out of this, because instead of getting a wildly growing curve, you'll get a curve that's pers, perhaps, maybe growing as a straight line. So, let's go back now and look at the three functions and do a log/log plot of them. [SOUND] Okay, let's finish off our example. So, here we are back in our Python code. Before I had this parameter, plot_type, which was just STANDARD. The cool thing is, we can actually change that and what you'll see up here is, instead of plotting the input value versus the counter, we'll plot the log of the input value versus the log of the counter. It'll do a log/log plot, so, I can change this to LOGLOG, and I'm going to hit Run. [SOUND] And, what comes out here is a plot, and what you can see here is that the log/log plot of this line is again a line. Probably something more interesting here is our second curve, our second curve, the one that we thought might be quadratic. Well, when we do the log/log plot, what we see is that, yeah, it's pretty much growing like a straight line. And in fact, if you look at it, it looks like the slope is two. So in fact, I think this is probably growing quadratically. This last one though, look, it's not growing as a straight line. I thought it might be cubic but it's not. So probably this, this last one is may not be a cubic, it may not be, may not even be a polynomial. So let's go back real quick and look at our functions and just kind of see what the mystery functions look like. [SOUND] So the first one is really simple, it was just going through and doing kind of just five iterations of interloop for every value and every value and input value range. So that's, that's 5x, it's linear easily. This one here, if you look at it was doing some plotting, but at the end of the day, it's kind of two nested loops, and this is, this is quadratic. This last one is actually, is, is, is actually not quadratic. In fact, you kind of see this magic 1.1 to some power. It's actually doing a very slowly growing exponential function. So, if we act, had turned up that our mystery function was actually growing in this rate, you probably wouldn't be able to run it for really large values. So we could kind of see that, when we did the log/log plot that we didn't get a straight line. So hopefully, this lecture has helped you to kind of get more knowledge about exponentials and logarithms, and giving you some insight into how we could go about analyzing the running time of our code, even if we can't do some kind of close analysis based on looking at the code. [SOUND]
