Timing Programs and Counting Operations
MIT 6.100L Intro to CS and Programming using Python, lecture 21, explained in plain English
Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.
Learn this lecture freeWatch or read the original lecture: MIT OpenCourseWare.
Part 1 · 0:00–10:00
This part explains why a program must be fast as well as correct, and introduces simple ways to measure how efficient a program is.
Key ideas
- A program has to be correct, and it also has to be fast. Large amounts of data make speed matter, because a slow program can take far too long to be useful. 1:16
- Efficiency has two parts: time efficiency (how long a program takes) and space efficiency (how much memory it uses). Usually, making one better makes the other worse. 2:22
- The Fibonacci example shows this tradeoff. The plain recursive version was slow, but the memoized version ran much faster because it stored values in a dictionary, which used more memory. 2:43
- We care more about the algorithm, which is the idea behind the scenes, than about one implementation, which is one way of writing that idea in code. 4:09
- To measure a program, you can record the system clock before and after running it and subtract the two times. You can also count the number of operations it performs. 9:34
Words to know
- memoization
- Saving results you have already worked out in a memo, such as a dictionary, so you do not have to calculate them again.
- epoch
- The starting point of time that computers count from, which is January 1, 1970. The time module counts seconds from this point.
- implementation
- One specific way of writing a program in code. Two different implementations can carry out the same underlying algorithm.
- module
- A file of ready-made functions and tools that you bring into your code, such as the time module, so you can use them.
Example
Imagine a student who writes each answer in a notebook the first time they work it out. The next time the same question comes up, they just read the answer instead of working it out again. That saves time but uses some notebook space, which is the same tradeoff memoization makes.
3 checked practice questions for this part are in the app.
Part 2 · 10:00–20:00
This part shows how to time Python programs, why timing alone is unreliable, and how counting basic steps gives a fairer way to compare algorithms.
Key ideas
- A time wrapper is a helper function that takes another function and a list of inputs. It runs that function on each input and prints how long each run took. 10:00
- Small inputs often look instant, but bigger inputs reveal the pattern. The square function reached 5 seconds at an input of only 10,000, while mysum needed 100 million to take that long. 14:25
- Timing is unreliable for comparing algorithms. Results change with the implementation, the computer, the language, and what else is running in the background. 15:30
- Counting operations gives a steadier measure. Each basic step, such as adding, comparing, assigning, or accessing memory, counts as one unit of time, no matter how fast it really is. 18:01
- Using this counting method, the Celsius to Fahrenheit function takes three units of time. It takes the same three units whether the input is 0 or 1 million. 19:28
Words to know
- wrapper function
- A function that wraps around another function to add extra behavior, such as timing it, without changing the inner function.
- algorithm
- A set of steps for solving a problem. The lesson says there are only a handful of these for any given problem.
- implementation
- One specific way of writing an algorithm in code. The same algorithm can be written as many different implementations.
- operation
- One basic action in a program, such as adding, comparing, or assigning a value.
Example
Think of timing a recipe with a kitchen clock. The time depends on your oven, your speed, and whether the phone rings during cooking. If you instead count the steps in the recipe, such as stirring, measuring, and pouring, you get a number that stays the same no matter whose kitchen you use.
3 checked practice questions for this part are in the app.
Part 3 · 20:00–32:04
This part shows how to count the basic steps a program takes, so you can predict how its work grows as the input gets bigger.
Key ideas
- Each simple step, like an assignment or an addition, counts as one operation. Loops repeat their steps, so you multiply to get the total. 20:00
- For the mysum function, the lesson counts 3x + 4 operations for an input x. Plugging in a number tells you the total steps. 21:01
- A loop inside another loop multiplies the work. The square function does about 3n squared plus 1 operations. 22:30
- Counting operations works better than timing, because the count stays the same on a slow or fast computer. 30:05
- For very large inputs, the small extra terms barely matter. What you care about is the order of growth, such as roughly linear or roughly n squared. 27:10
Words to know
- operation
- One simple step the computer does, like assigning a value to a variable or adding two numbers.
- nested for loop
- A for loop placed inside another for loop, so the inner loop runs again every time the outer loop runs once.
- steady state
- The pattern a set of results settles into when the input gets very large.
- counter
- A variable that goes up by one each time a step runs, so the program can keep track of how many steps it has done.
Example
Imagine a teacher who checks each paper three times, and then does a few quick tasks at the end. With 10 papers, those few extra tasks are a big part of the work. With 10,000 papers, they hardly change the total, so the teacher's work mostly grows with 3 checks per paper.
3 checked practice questions for this part are in the app.
← Lecture 19: Inheritance · Lecture 22: Big Oh and Theta →
Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.
LessonBound · Free lecture notes · Privacy · Terms · New York