Not all programs are created equal. Â In this course, we'll focus on writing quality code that runs correctly and efficiently. Â We'll design, code and validate our programs and learn how to compare programs that are addressing the same task.

Loading...

From the course by University of Toronto

Learn to Program: Crafting Quality Code

278 ratings

Not all programs are created equal. Â In this course, we'll focus on writing quality code that runs correctly and efficiently. Â We'll design, code and validate our programs and learn how to compare programs that are addressing the same task.

From the lesson

Week 3

- Jennifer CampbellAssociate Professor, Teaching Stream

Department of Computer Science - Paul GriesAssociate Professor, Teaching Stream

Department of Computer Science

Up to now, our primary focus has been on writing correct code.

Â Next, we'll analyze our algorithms to determine the amount of time that they

Â take to run, relative to the size of the input.

Â In up coming lectures, it'll apply what you learned in this one, to analyze

Â algorithms and compare them in order to determine which one to use.

Â To analyze our algorithms, we're not going to measure them by timing them.

Â Instead, we're going to read the code and look at the number of steps that they'll

Â take for a particular input size. For example, in this lecture, we're going

Â to write several functions that print integers, and we're going to focus on how

Â many times the print function is called in each of our functions.

Â The first function that we'll analyze is print ints.

Â This function prints the integers from 1 up to n inclusive.

Â Let's call this function. We'll run the module and call print_ints

Â with an argument of ten. In this case, the print function is

Â called ten times. That is, the for loop iterates ten times.

Â What if this function were called with the argument 20?

Â In that case, the for loop would iterate 20 times, and he print function would be

Â called 20 times. And what about 40?

Â There would be 40 iterations of the loop. Let's plot this so that we have a visual

Â representation of the run time. On one axis, we'll have n, the input to

Â the function. And on the other axis, we'll have the

Â number of steps that the function will execute for a given n.

Â For this problem, the steps that we're measuring are the print function calls.

Â Notice that the number of steps is proportional to the size of n.

Â Next, let's consider another function. Print odd ints, prints the odd integers

Â from one to n inclusive. We'll call this function for the argument

Â 10 as well. Print was only count five times.

Â If the argument were 20, it would be called ten times.

Â And if the argument were 40, it would be called 20 times.

Â For the first function, the number of print function calls was equal to n.

Â For this one, it's roughly half of n depending on whether n is odd or even.

Â [UNKNOWN] this as well. We can see that the number of steps still

Â proportional to the size of n, it's roughly half of n.

Â This function and the first are both considered linear functions.

Â The run time grows linearly with respect to the size of the input n.

Â Next up, we'll analyze function print pairs.

Â It prints all combinations of pairs of integers from 1 to n, inclusive.

Â We're going to start by calling this function a couple of times.

Â First, we'll call print pairs with an argument 2.

Â In that case, four pairs are printed. We'll call it again with the argument 3.

Â In this case, we've got 9 pairs being printed.

Â Now, with the argument 4, there are 16 pairs printed.

Â Do you see a pattern? For the argument n, the print function is

Â called n squared times. When analyzing algorithms, we don't

Â always have the luxury of running code. Sometimes, we do analysis before writing

Â code. To determine whether it's even worth

Â writing, we'll analyze this function by reading the code, and the same could be

Â done with pseudo code. The print function call is inside the

Â inner loop of a nested loop. When the inner loop is executed, it will

Â iterate n times. And the inner loop is executed once for

Â each iteration of the outer loop. The outer loop will execute n times as

Â well. So with n iterations of the outer loop

Â times n iterations of the inner loop, print is called n squared times.

Â This time, the number of steps is proportional to the size of the input

Â squared. We'll plot this as well.

Â As n grows, the number of steps is growing more quickly than it did for the

Â other 2 algorithms. If we had 2 algorithms that solved the

Â same problem and one had linear run time while the other had quadratic run time,

Â we'd want to use the one with linear run time if we were trying to pick the most

Â efficient algorithm. Let's consider one more function.

Â This function, print double step, also prints the integers from 1 to n

Â inclusive. But rather than using a step size of one

Â or two, like the previous functions, this step size varies.

Â The step size is the difference between a pair of numbers in the sequence.

Â The initial step size would be 1. The next step would be 2, then 4, 8, 16,

Â 32 and so on. Let's consider how many integers are

Â printed for various values of n. Let's start with n equal to 4.

Â In that case, three integers would be printed.

Â The integers 1, 2 and 4. How about when n refers to 5?

Â In that case, there would still only be three integers printed, the ints 1, 2,

Â and 4. The same goes for when n refers to 6 and

Â 7. It's not until n refers to 8 that that we

Â then have a fourth integer printed. When n refers to the values 8 through 15,

Â there are still only four ints printed. It's only when n refers to 16 that there

Â would be a fifth int printed. And then, when n refers to 32, twice

Â that, six would be printed. When it's twice that, 64, seven would be

Â printed. Every time n is doubled, an additional

Â integer is printed. For the previous function, we said the

Â number of steps is equal to n squared. For this function, the number of steps is

Â proportional to log base 2 of m. This algorithm is logarithmic.

Â As the side of n grows, the number of steps grows more slowly than it did for

Â the linear and quadratic algorithms.

Â Coursera provides universal access to the worldâ€™s best education,
partnering with top universities and organizations to offer courses online.