Lecture notes · Math for Computer Science · Lecture 13

Sums and Asymptotics

MIT 6.042J Mathematics for Computer Science, lecture 13, 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

The professor sets up a stacking-blocks challenge, asking whether a block can be stacked all the way out past the edge of a table, and says today's math will be used to study it.

Key ideas

Today the class uses methods for analyzing sums and finding closed-form expressions, which are short formulas that give the total of a long sum, to solve famous problems. One of them is stacking blocks and balancing the center of mass. 0:26
In theory, a stack stays up as long as its center of mass, the balance point of the whole stack, sits anywhere over the block below it. In practice, air movement and bumps can knock it over if it is near the edge. 1:29
The main question is whether you can stack blocks so that one block goes all the way off the edge of the table. Each level can hold only one block, and the stack must stay stable on both sides. 2:11
The rules are one block per level, and the stack must stand up by itself. You are allowed to build back and forth to help your balance. 2:53
The TAs got a block out over the edge of the table during the contest. The professor says this one will be hard to analyze, so the math is still to come. 8:11

Words to know

center of mass: The balance point of a whole object or stack. If it stays over the support below, the stack does not tip.
stable: Steady and not likely to fall over. A stable stack can stand up on its own without someone holding it.
closed-form expression: A short formula that gives the answer to a long sum directly, so you do not have to add up every piece one by one.
overhang: Not used in this part by name, so skip it. The idea is simply how far a block sticks out past the one under it.

Example

Think of stacking books on the edge of a desk. Each book can sit farther out than the one below, but the pile must still balance over the book it rests on. If you push too far, the whole stack tips over, just like the blocks in the lecture.

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

Part 2 · 10:00–20:00

This part shows how to stack blocks as far out over a table edge as possible without the stack tipping, and begins a way to work out how far that reaches.

Key ideas

A greedy algorithm means taking the biggest step you can at each moment and never going back. Here, the top blocks are pushed out as far as they can go, one group at a time. 11:25
A stack stays up only if the center of mass (the balance point) of the top blocks sits over the block below. If it sits past that block's edge, the stack tips. 15:24
With the greedy stacking, the balance point of the top k blocks lands exactly on the edge of block k+1. That is the furthest it can go without falling. 17:06
The balance point of one block by itself is half a block from its right edge, so it sits at r_k minus 1/2. The balance point of the top k blocks can then be found by averaging this with the balance point of the top k minus 1 blocks. 18:53
The lesson sets up a recursion: a formula for the balance point of k blocks that uses the answer for k minus 1 blocks. This part of the lesson ends before the formula is finished. 19:45

Words to know

center of mass: The balance point of an object or group of objects. If you could support it at that point, it would not tip.
greedy algorithm: A step-by-step method that always takes the biggest possible step right now and never goes back to change earlier choices.
stability constraint: The rule that a stack stays up only if its balance point lies on the block beneath it.
recursive formula: A formula that works out a value using the value for a smaller case, such as the answer for k minus 1 blocks being used to find the answer for k blocks.

Example

Think of stacking books on the edge of a table to hang one over the side as far as possible. You slide the top book out until its balance point is just at the edge, then slide the stack above it out the same way. If you push any further, the whole pile tips over.

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

Part 3 · 20:00–30:00

This part shows how the stacking-blocks puzzle turns into a sum of fractions, called the harmonic sum, and why that sum grows very slowly.

Key ideas

Using the greedy strategy (each block is placed right at the edge of the block above it), the gap between block k and block k plus 1 simplifies to 1 over 2k. The lesson works this out step by step. 21:57
When you add all these gaps together, the middle terms cancel. That leaves only how far the top block sticks out, which is one half of the sum of 1 over i for i from 1 to n. 24:13
The bottom block has nothing below it to hang over, so its overhang is zero. That lets us say the top block's overhang is exactly half of the harmonic number H_n. 24:59
H_4 is about 2.08, which is bigger than 2. So half of it is bigger than 1, meaning four blocks are enough (in theory) for the top block to hang off the table. 26:33
The harmonic numbers keep growing without limit, but very slowly. A million blocks only let the top block reach about seven block-lengths out, and there is no known closed-form expression for the sum, so we estimate it with integration bounds. 28:02

Words to know

harmonic number: The total you get when you add up fractions 1 over 1, 1 over 2, 1 over 3, and so on, up to some number n. The lesson writes it as H n.
closed-form expression: A neat formula that gives the answer directly, without having to add up every piece one by one.
greedy strategy: A way of solving a problem by making the choice that looks best at each step. Here, each block is placed as far out as it can go over the block below.
integral: A tool from calculus for finding the total area under a curve. The lesson uses integrals to estimate sums that have no closed form.

Example

Picture a pile of books on a table, each one slid a little further out than the one under it. Each new book adds only a small extra overhang, and the small amounts add up to a total that keeps growing. The harmonic sum works the same way: each new fraction is tiny, but together they slowly add up to more and more.

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

Part 4 · 30:00–40:00

This part shows how to estimate big sums and products using the area under a curve, with two examples: the harmonic numbers and n factorial.

Key ideas

The integral (the area under a curve) can trap a sum between two bounds. For the harmonic number, the lesson gets log of n on the bottom and 1 plus log of n on the top, so the sum is very close to log n. 30:42
The harmonic number grows about as fast as log n. The lesson writes this with tilde notation, which means 'grows at about the same rate as.' 31:03
Using the greedy block-stacking strategy, reaching 100 blocks out means the harmonic number must reach 200. That needs about e to the 200 blocks, which is an enormous number. 33:20
A product like n factorial can be turned into a sum by taking the log of it. Once it is a sum, the same tools for sums work on it. 36:24
For log of n factorial, the lesson uses the integral of log x, which is x ln x minus x. Plugging in n and 1 gives bounds that are close to the true value. 38:54

Words to know

harmonic number: The sum 1 + 1/2 + 1/3 and so on, up to 1/n. It is the total you get by adding those fractions.
factorial: n factorial, written n!, is the product of all whole numbers from 1 up to n. For example, 4! is 1 times 2 times 3 times 4.
natural log: A special kind of logarithm, written ln or log here. It answers the question: what power must the number e be raised to, to get this number?
closed-form expression: A simple formula you can plug a number into to get the answer directly, without adding up every term one by one.

Example

Imagine trying to find the total area under a hill by drawing rectangles. Rectangles that stick above the curve give you an upper estimate, and rectangles that stay under it give you a lower estimate. The true total must lie between the two, so you get a trustworthy range without an exact answer.

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

Part 5 · 40:00–50:00

This part shows how to estimate how fast n factorial grows using Stirling's formula, then introduces big O notation for comparing how fast functions grow.

Key ideas

Taking logs and then exponentiating gives rough bounds on n factorial. The result is that n factorial is about n divided by e, raised to the power n, which is a quick, fairly close estimate. 40:46
Stirling's formula is a much tighter estimate of n factorial. The lecturer says it is worth keeping on your crib sheet for the midterm. 41:08
Stirling's formula has an extra error term that approaches 1 as n gets large, so it can be dropped. This simpler version is written with a tilde, which means the two sides are roughly equal for large numbers. 42:00
Big O notation says one function does not grow faster than another, once you ignore constant factors and look at large inputs. You check this by looking at the limit of the ratio f over g. 46:13
To prove that f is O(g), take the limit of f divided by g as x goes to infinity and show that it does not blow up to infinity. The example uses x and x squared, where the ratio goes to 0. 49:44

Words to know

Stirling's formula: A formula that gives a very close estimate of n factorial, using e and the square root of 2 times pi times n.
Tilde notation: A short way to write that two functions are roughly equal when x gets very large, meaning the ratio between them goes to 1.
Big O notation: A way to say that one function grows no faster than another, ignoring constant multipliers, when the input gets large.
Limit: The value a function gets closer and closer to as the input keeps getting bigger, like x going to infinity.

Example

Think of two runners, one who runs at a steady pace and one who doubles their speed every minute. After a long race, the steady runner can never catch up, so the first is 'big O' of the second in terms of how fast they grow. Big O is just a way of saying which function is always at most as fast as another, no matter how big the input gets.

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

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

This part explains how to tell whether one growth rate is capped by another, using the limit test and the rule that constant factors and smaller terms can be ignored.

Key ideas

To check whether one function is O of another, take the limit of their ratio as the input goes to infinity. If the limit is less than infinity, the first function is O of the second. 50:02
Constant factors do not matter in big O. Multiplying by a number like a million changes nothing, so 10 to the sixth times x is O of x squared, and x squared is not O of a million times x. 51:26
Smaller terms do not matter either. A polynomial like x squared plus 100x plus 10 million is O of x squared, because the lower-order parts fade away as x gets large. 52:31
Any polynomial grows slower than any exponential. So x to the tenth is O of e to the x, but 4 to the x is not O of 2 to the x, even though 4 looks like only double 2. 58:10
Computer scientists use big O to avoid details about the machine or how steps are counted. Matrix multiplication takes O of n cubed steps, which captures the important growth rate. 54:27

Words to know

big O: A way of saying one function grows no faster than another, ignoring constant factors and smaller terms.
limit: The value a ratio gets closer and closer to as the input becomes very large.
polynomial: An expression built from powers of x with numbers in front, such as x squared plus 3x.
exponential: A function where the input is the power, such as e to the x or 2 to the x. These grow very fast.

Example

Picture two savings accounts. One adds 10 dollars every month, and the other doubles every month. Even if the first one starts with more money, the doubling account eventually leaves it far behind, which is the same idea as any polynomial being beaten by any exponential.

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

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

This part explains three shorthand symbols (big O, big omega, and theta) that describe how fast a function grows, and warns about common misuses of them.

Key ideas

The tilde symbol means two things grow at the same rate in the limit, so the ratio of the two goes to 1. Because of that, small extra terms like +10 can be hidden inside a tilde, which can make a statement technically true but misleading. The lecturer says to move the small terms outside the tilde. 1:01:00
Big O is an upper bound. It says a function grows no faster than another. You cannot use big O to mean a lower bound, even though some people do it. 1:03:12
Big omega is the lower bound symbol. It is the opposite of big O: f is O(g) exactly when g is omega of f. 1:04:24
Theta means both at once: a function is theta of another when it is both big O and big omega. This means the two grow at the same rate, not just at most or at least that rate. 1:06:49
Constants and low-order terms do not matter for these symbols, so 10x cubed minus 20x plus 1 is theta of x cubed. But x divided by log x is not theta of x, because the limit of their ratio is 0, not a number greater than 0. 1:08:18

Words to know

big O: A way to say a function grows no faster than another function, like an upper limit on growth.
big omega: A way to say a function grows at least as fast as another function, like a lower limit on growth.
theta: A way to say two functions grow at the same rate, because they are both big O and big omega of each other.
tilde: A symbol meaning the ratio of two things goes to 1 as the input gets very large, so they are roughly the same size in the long run.

Example

Think of two people saving money. One adds 100 dollars a month and the other adds 1 dollar a month, so the first grows much faster. Ignoring small fixed amounts, the savings growth is the main thing to compare, which is the idea behind leaving out constants and small terms.

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

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

This part explains two more growth symbols, little o and little omega, and then shows a false proof that warns against misusing big O.

Key ideas

Little o means one function grows strictly slower than another. You check this by taking the ratio of the two functions and seeing that the limit goes to 0. 1:11:52
Little omega is the opposite: one function grows strictly faster than another. The ratio's limit goes to infinity. 1:12:18
Constant factors do not count. For example, x over 100 is not little o of x, because the ratio's limit is 1 over 100, which is not 0. Theta still covers it, because the two functions grow at the same rate. 1:13:31
x squared is little omega of x, because the ratio of x squared to x goes to infinity. Little omega says more than big omega here. 1:14:12
The lecturer then uses induction to 'prove' that adding up the numbers from 1 to n is O(n). The proof looks fine, but the claim is false, because that sum grows like n squared, and n squared is not O(n). The lesson leaves the exact mistake for you to find. 1:17:10

Words to know

little o: A way of saying one function grows strictly slower than another. Equal growth rates do not count.
little omega: A way of saying one function grows strictly faster than another. Equal growth rates do not count.
limit: The value a ratio gets closer and closer to as the input gets bigger. Here the ratio is either shrinking to 0 or growing to infinity.
induction: A proof method that checks a first case, then shows that if a statement holds for n, it also holds for n plus 1.

Example

Think of two runners, one who runs at a steady pace and one who is always slower and falls further behind. If you divide the slow runner's distance by the fast runner's distance over time, that ratio keeps shrinking toward 0. That is the idea behind little o: one function falls further and further behind the other.

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

Part 9 · 1:20:00–1:23:34

This part explains why you should never put big O notation inside a proof by induction or inside a predicate, because the function disappears and false results can follow.

Key ideas

Asymptotic notation, such as big O, only works on functions. It describes how a function grows as its input gets large, so it does not apply to a plain number. 1:20:00
Once you fix n to one specific value, like n equals a million, the expression is no longer a function. It is just a single number, called a scalar. 1:22:07
A single fixed value can still be called O of 1, but only because it is a constant. That does not make a statement about a function's growth. 1:22:07
Putting big O inside a predicate, which is a statement that is either true or false about a value, loses the function. This lets you prove false things, so the lecturer says never to use asymptotic notation in induction or predicates. 1:22:54

Words to know

big O: A shorthand that says how fast a function grows compared to a simpler function, such as n. Saying a function is O of n means it grows no faster than a constant times n, once the input is large.
asymptotic notation: The family of shorthand symbols, including big O, used to describe how a function behaves when its input gets very large.
scalar: A single plain number, as opposed to a function that gives a different output for each input.
predicate: A statement that is either true or false, such as a claim about a value in a proof.

Example

Think of a speed camera that records how a car's speed changes over a long road trip. That full record is a pattern you can study, but a single reading taken at one moment is just one number. Asking whether one number 'grows' tells you nothing, which is why big O needs a whole pattern, not one value.

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

← Lecture 11: Relations, Partial Orders, and Scheduling · Lecture 16: Counting Rules I →

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