Lecture notes · Programming in Python · Lecture 22

Big Oh and Theta

MIT 6.100L Intro to CS and Programming using Python, lecture 22, 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 free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

This part shows how to measure how long a program takes to run, and how changing the inputs can change that time.

Key ideas

The lesson uses the performance counter, which measures time much more finely than the older time function. This lets it pick up very small runtimes that used to show as zero. 2:19
To time a function, record a starting time, run the function, record a stopping time, then subtract the starting time from the stopping time. The difference is how long the function took. 3:00
The convert_to_kilometers function takes about the same time no matter what input it gets. Its runtime is around 3 times 10 to the negative 7 seconds. 6:41
In compound, changing the monthly investment or the interest rate does not noticeably change the runtime. Changing the number of months does. 9:13
When the number of months grows by 10 times, the runtime also grows by about 10 times. Each run gives slightly different numbers, so the exact times will vary. 9:37

Words to know

performance counter: A timer in Python that measures very short amounts of time. It is used to find out how long a program or function takes to run.
precision: How small a measurement can be and still be shown accurately. Higher precision means finer detail.
scientific notation: A short way to write very large or very small numbers using powers of 10, such as 4.3 times 10 to the negative 6.
parameter: An input that a function accepts, like the miles given to convert_to_kilometers.

Example

Think of timing a race with a stopwatch. A watch that shows only whole seconds will read zero for a very quick sprint, but a watch that shows hundredths of a second can catch the real time. The performance counter works like the more precise watch.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

This part compares how the run time of programs grows as their input gets bigger, using a compound interest function and list functions.

Key ideas

For the compound interest function, only the number of months changed the run time. Changing the starting money or the interest rate did not change it. 10:21
The input is only really measured by its size. Run times are easier to read when the input is large, because small runs can be thrown off by other things the computer is doing. 11:03
For the sum function, the input is a list, so its size is how many items are in the list. When the list gets 10 times longer, the run time gets about 10 times longer too. 15:40
Two functions can do very different jobs but still be the same in terms of algorithm, meaning the same way their run time grows. Both use a loop that goes through the input once. 18:07

Words to know

input: The information you give to a function so it can do its work, such as a number or a list.
for loop: A set of steps the computer repeats once for each item or count, such as going through each number in a list one at a time.
brute force: A method that tries every option one at a time, without any clever shortcuts.
algorithmically: Looking at how a method works step by step, and how its run time grows, rather than at what the method is for.

Example

Think of a cashier who scans each item in your cart one at a time. If you have 10 times as many items, it takes about 10 times as long to check out, no matter what the items are. The cashier's speed for each item is what decides how the total time grows.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part compares three ways to check whether an item is in a list, and shows that binary search is far faster than checking one item at a time.

Key ideas

Binary search starts by checking the middle item of the list. Each check cuts the search area in half, so it finds the answer much faster. 20:00
To compare the three methods fairly, the lecturer averages the timing for the item being first, in the middle, and last in the list. This covers the best, middle, and worst cases. 22:27
Brute force checks items one at a time. When the list gets 10 times longer, the search takes about 10 times as long. 24:37
On a list of about 100 million items, brute force took 1.6 seconds, but binary search took about 0.00001 seconds. That is orders of magnitude faster, not just a little faster. 27:29
Python's built-in in operator is about twice as fast as the lecturer's own loop. It still grows at the same rate as the list grows. 28:38

Words to know

binary search: A search that checks the middle item of a sorted list and then throws away the half that cannot contain the answer, repeating until it finds the item or runs out of list. It is also called bisection search.
linear: Growing at the same rate as the input. If the list gets 10 times bigger, the time also gets about 10 times bigger.
integer division: Dividing and then rounding down to a whole number, written with // in Python. It is used here so the middle position is a whole number.
built-in: Already part of Python, so you do not have to write it yourself. The in keyword is an example.

Example

Imagine finding a name in a printed phone book. You open to the middle, see whether the name comes before or after that page, and tear away the half that cannot have it. Repeating this finds the name in far fewer steps than reading every name from the first page.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part explains a function that finds the longest distance between any two points, and why its running time grows much faster as the input gets bigger.

Key ideas

The diameter function looks at a set of points on a flat 2D plane and finds the biggest distance between any two of them. 30:19
It uses nested for loops: an outer loop picks one point, and an inner loop compares that point with the others. 30:41
The inner loop starts at i plus 1, so each pair of points is checked only once and the point itself is skipped. 32:08
When the input size doubles, the running time roughly quadruples, which is a quadratic pattern, so this function is far slower than the list search examples. 37:35
Plotted on a graph, the list search time grows in a straight line (linear), while the diameter time curves upward (quadratic). 39:42

Words to know

nested for loops: One loop that runs inside another loop, so the inner loop finishes all its steps for each step of the outer loop.
tuple: A small group of values kept together in one pair or set, like the x and y position of one point.
magnitude: How big something is. Here it means how large a distance is.
quadratic: A pattern where doubling the input makes the work about four times as large, so the time grows faster and faster.

Example

Think of a group of friends at a party who each want to shake hands with every other friend once. The first person shakes hands with everyone else, then the second person shakes hands with the people who are left, and so on. Adding a few more people makes the total number of handshakes grow much faster than the number of people, just as the diameter function's work grows faster than its input.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–50:00

This part explains why timing a program alone is not enough, and how counting basic steps gives a formula for how long a program will take as its input grows.

Key ideas

Timing a program on different computers gives different raw numbers. The pattern of growth stays the same, though: if the input grows by 10 times, the work grows by about 10 times on any machine. 41:02
To find a pattern without relying on the machine, we count basic steps such as math, comparisons, indexing, and assignments. We treat each one as taking the same fixed amount of time, called constant time. 43:35
A function that always does the same number of steps, like convert to kilometers, does not depend on the input size at all. Its count is always 2. 44:42
The sum function does 3 steps for each item in the list, plus 2 more steps for the setup and return. That gives a formula of 3 times the list length, plus 2. 46:11
A global variable is a shared variable that any function can change. The lecturer says it is usually very bad programming, but a counter for counting steps is one case where it is acceptable. 47:36

Words to know

asymptotic complexity: A way of describing how the work a program does grows as the input grows, without having to run it.
operation: One small basic step in a program, such as an addition, a comparison, or an assignment.
global variable: A variable defined outside any function that every function in the program can read and change.
logarithmic: A pattern where the work grows slowly, so each big jump in input adds only a little more work.

Example

Think of counting the steps you take to walk a hallway. If the hallway has 10 doors and you check each one, the total steps grow in a steady way with the number of doors. Counting steps like this lets you predict how long the walk will take without actually walking it.

3 checked practice questions for this part are in the app.

Part 6 · 50:00–1:00:00

This part explains how to describe how fast a program's work grows as its input gets bigger, and why we ignore small details to do it.

Key ideas

A counter can track how many operations a program does. Counting shows an exact link between the input size and the work, such as 3x plus 4. 50:21
For very large inputs, the exact numbers matter less than the biggest term. We focus on the part that grows fastest and drop constants and small extra amounts. 53:00
The goal is the order of growth: how the runtime changes as the input gets really big. Exact timings like 1.3 times 10 to the negative 6 seconds do not matter for this. 53:45
Before measuring, decide which input affects the runtime. In the is-in example, the length of the list matters, but the value of the element being searched for does not. 57:30
This class looks at the worst case, which for is-in is when the element is not in the list at all. Big O and big theta are the notations used to write this order of growth. 57:52

Words to know

order of growth: How fast the amount of work rises as the input gets bigger.
worst case: The hardest situation a program could face, which this class always measures.
big O: A notation that writes down an upper bound on how fast a program's work grows.
logarithmic: A growth pattern that rises slowly, the kind the lecture found for binary search.

Example

The lecturer checks whether 0 is in a list of 3 numbers, then in a list of 10 numbers. The longer list can take more steps, so the list length matters. The actual numbers inside do not change the work, so they are left out of the measurement.

3 checked practice questions for this part are in the app.

Part 7 · 1:00:00–1:10:00

This part explains how to describe how fast a function grows, using big O (an upper limit) and theta (an upper and lower limit) by keeping only the fastest-growing term.

Key ideas

Big O is an upper bound. It is a simpler function that stays above the original function once the input is large enough, past a crossover point. 1:00:19
Constant multipliers and small parts are dropped, because only very large inputs matter. Behavior at small inputs is not important. 1:02:35
Big O alone is not very useful, because many functions that grow much faster also count as upper bounds, so you could pick something silly. 1:05:18
Theta is stricter: the same simple function must be both an upper bound and a lower bound. Then it is the fastest-growing term that sets the answer. 1:07:13
To find the order of growth, find the dominant term, which is the part that grows fastest for big inputs. Drop the constants and the other terms. 1:08:37

Words to know

big O: A way to say a function grows no faster than some simpler function, once the input is big enough. It is an upper limit.
theta: A tighter way to describe growth. A simple function that is both an upper limit and a lower limit for the original function.
upper bound: A function that sits above the one you are studying, at least for large inputs, like a ceiling over it.
dominant term: The part of a formula that grows fastest and eventually matters most when the input gets very large.

Example

Think of a phone bill that is 3 times your minutes squared plus 20 times your minutes plus 1. For a very long call, the squared part takes over and mostly decides the total, so the bill is best described by the squared part alone. The smaller pieces and the multiplier matter much less at that scale.

3 checked practice questions for this part are in the app.

Part 8 · 1:10:00–1:20:28

This part shows how to describe how a program's running time grows, using Big Oh-style labels called theta, based on the input the program takes.

Key ideas

Theta describes how the running time grows, and it is measured against the function's input. That input is not always n, so you have to name the right input, such as the length L of a list. 1:10:00
To find theta, keep only the term that grows the fastest and drop any multiplicative constants (fixed numbers multiplied in front). If the function has two inputs, keep the dominant term for each one. 1:10:45
The law of addition: when parts run one after another, add their thetas and keep only the bigger one. For example, theta of n plus theta of n squared simplifies to theta of n squared. 1:13:41
The law of multiplication: when one loop sits inside another, multiply their thetas. Two loops that each depend on n give theta of n squared, even if the inner loop only runs half of n. 1:15:06
Programs fall into rough groups from fast to slow: constant, logarithmic, linear, log linear, polynomial, and exponential. A good first version usually lands in the faster groups, and polynomial or exponential programs get slow quickly. 1:19:15

Words to know

theta: A label that says how fast a program's running time grows as its input gets bigger. It ignores small fixed details and keeps the main growth pattern.
dominant term: The part of a formula that grows the fastest, so it matters most when the input is large. For example, in n squared plus n, the n squared is the dominant term.
multiplicative constant: A fixed number multiplied in front of a variable, like the 5 in 5n. Theta ignores these numbers.
polynomial: A running time where the input is raised to a fixed power, like n squared or n cubed. These get slow quickly as the input grows, though they are less slow than exponential ones.

Example

Think of a checkout line where each person takes the same time to serve. If there are L people, the total time grows in step with L, so you would call it theta of L. If you added a second line that you had to finish after the first, you would add the two times and keep only the bigger part.

3 checked practice questions for this part are in the app.

← Lecture 21: Timing Programs and Counting Operations · Lecture 24: Sorting Algorithms →

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