This course is about algorithms that never simply solve for the answer in one step. Instead, each one produces a whole list of guesses -- a first guess, a better one, a better one still -- and the entire theory of whether a method "works" comes down to what happens to that list as it keeps going. Talking about that precisely needs two ordinary tools with a specific new job: the limit of a sequence, to say what "the guesses settle down" means exactly, and big-O notation, to compare how fast two quantities grow or shrink without committing to their exact values. Both ideas are genuinely new territory for this course, not a review of material taught elsewhere -- this section is where they get their name.
Think of a sequence of guesses the way you'd think of repeatedly guessing a stranger's age, refining your guess after each new hint: 40, then 35, then 33, then 32.5, each one a little closer than the last. Saying the sequence "converges to 32" means that no matter how tight a window you draw around 32 -- within five years, within one year, within one month -- your guesses eventually stay inside that window forever, not just visit it once and wander back out. Big-O notation answers a completely different question: not "where does this end up," but "how fast is it growing." Saying a task's cost is O(n^2) means that once the input is large enough, doubling the input roughly quadruples the work, and it doesn't matter whether the exact cost is 3n^2 or 3n^2+50n -- the n^2 part is what dominates for a large enough n, and big-O notation is just the agreed-on way of saying "ignore everything but that dominant part."
A sequence here is an ordered list of guesses produced one at a time, written x^{(0)},x^{(1)},x^{(2)},\dots, with the superscript in parentheses naming which step produced that value (never an exponent — x^{(2)} is "the guess after step 2," not x squared). The sequence converges to a limit x^\ast, written \lim_{k\to\infty}x^{(k)}= x^\ast, if the terms get and stay arbitrarily close to x^\ast as k grows without bound: for every tolerance you name, no matter how small, every term from some point onward lands within that tolerance of x^\ast. Big-O notation compares the growth of two quantities without pinning either one down exactly: f(n)=O(g(n)) means f(n) is bounded above by some constant multiple of g(n) once n is large enough, i.e. there exist constants c>0 and n_0 with f(n)\le c\,g(n) for every n\ge n_0. The two ideas answer different questions -- a limit asks "does this sequence settle down, and to what," while big-O asks "how fast does this quantity grow (or shrink) compared to a reference function" -- and this course uses big-O for both computational cost (how many operations an algorithm needs as the problem size n grows) and convergence rate (how fast an error term \|x^{(k)}-x^\ast\| shrinks as the iteration count k grows).
A sequence of guesses settling down
Drag the ratio slider below 1 in size and watch the terms shrink toward 0, staying closer and closer forever after -- that settling-down, never wandering back out, is exactly what convergence means.
Loading interactive…
Trapped inside a shrinking tolerance band
This is x^{(k)}=1+0.6^{k}, converging to L=1. Shrink the tolerance band around L and watch every later term stay trapped inside it, no matter how tight the band gets.
Loading interactive…
Worked example
Confirming a limit and a big-O bound
-
1
Show that x^{(k)}=3+\dfrac{2}{k} converges to 3, and that f(n)=4n^2+7n is O(n^2).
-
2naming HOW large k needs to be is what turns "gets close" into a proof
As k\to\infty, \dfrac{2}{k}\to0, so x^{(k)}=3+\dfrac2k\to3+0=3. For any tolerance \varepsilon>0, choosing k>2/\varepsilon guarantees \left|\dfrac2k\right|<\varepsilon, so every term from that point on stays within \varepsilon of 3.
naming HOW large k needs to be is what turns "gets close" into a proof
-
3
For the big-O claim, compare f(n)=4n^2+7n to g(n)=n^2: for every n\ge1, 7n\le7n^2, so f(n)=4n^2+7n\le4n^2+7n^2=11n^2.
-
4
\boxed{x^{(k)}\to3\text{ as }k\to\infty;\quad f(n)=4n^2+7n=O(n^2)\text{ with }c=11,\ n_0=1.} The constant 11 and the threshold n_0=1 aren't unique -- any valid pair works -- big-O only claims that some such pair exists.
Where this goes next
Every convergence claim and cost estimate in this course
Every time a later chapter says "gradient descent converges linearly" or "Newton's method converges quadratically," it's making a claim in exactly this section's language: a statement about how fast \|x^{(k)}-x^\ast\| shrinks as k\to\infty, stated with a big-O bound. Every time a later chapter says "the simplex method runs in O(2^n) time in the worst case but O(n^3) in practice," it's making a claim about how the number of operations scales with the problem size n, using the same notation for a completely different quantity. Learning to read both claims correctly, and to keep straight which variable (the iteration count k, or the problem size n) each one is talking about, pays off on nearly every page from here forward.
Check your understanding (counts toward your progress)
Which of the following is the most useful reason to use big-O notation instead of an exact formula for an algorithm's cost?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Big-O deliberately throws away the exact constants and lower-order terms -- it is LESS precise than an exact formula by design, not more.
Big-O is a theoretical comparison tool, not a substitute for actually timing an implementation when the constants matter.
Big-O applies to every growth rate, from constant time up through exponential and beyond -- it isn't restricted to any one case.
Why
Big-O's whole value is abstracting away implementation-specific constants and slower-growing terms, letting two algorithms be compared by their dominant growth behavior alone.
Is 2n equal to O(n^2)?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
They don't grow at the same rate at all -- n^2 eventually dwarfs 2n, which is exactly why the bound holds.
Big-O compares any two functions of the same variable, not just a function to itself.
One matching point isn't the reason -- the bound 2n\\le n^2 has to hold for EVERY n past some threshold, which it does here for all n\\ge2.
Why
A slower-growing function is always O of a faster-growing one; 2n growing linearly while n^2 grows quadratically is exactly the kind of pair big-O notation is built to compare.
An algorithm's cost is measured as O(n) for input size n, while a second algorithm's cost is O(n^2). For large enough n, which statement is best supported?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Two different big-O bounds describe two different growth rates -- they aren't a claim of equal cost.
Big-O is silent about small n -- for a small enough input, the "worse" bound could easily still be cheaper in practice.
A big-O bound is exactly a statement about relative growth, which is precisely what determines which algorithm eventually wins as n grows.
Why
O(n) growing linearly and O(n^2) growing quadratically means that once n is large enough, the linear algorithm's cost falls behind the quadratic one's -- though for small n, the comparison can go either way.
A sequence x^{(k)} satisfies x^{(k)}=5 for every even k and x^{(k)}=5+1/k for every odd k. What happens as k\to\infty?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
The terms don't need to EQUAL the limit to converge -- they just need to get arbitrarily close and stay close, which both the even and odd terms do here.
There's no reason to average two patterns that are converging to the same place -- both already approach 5 on their own.
Nothing about this sequence grows without bound -- every term stays within 1 of 5 from the very first step.
Why
Both subsequences (even-indexed and odd-indexed terms) approach 5, and since every term eventually falls within any chosen tolerance of 5, the whole sequence converges to 5.
A sequence of errors satisfies \|x^{(k)}-x^\ast\|\le 3(0.5)^k for every k. What can you conclude?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
An upper bound that itself shrinks to zero is exactly enough to force the quantity it bounds to shrink to zero too.
The bound is directly on the DISTANCE to x^\ast -- once that distance shrinks to zero, the only place left for the sequence to converge to is x^\ast itself.
3 is a fixed constant, not a growing one -- it's the (0.5)^k factor that dominates and forces the whole bound to 0.
Why
Since 3(0.5)^k\to0 as k\to\infty and \|x^{(k)}-x^\ast\| is squeezed below it (and above 0, since it's a distance), the error itself must shrink to 0, meaning x^{(k)}\to x^\ast.
Check your understanding (counts toward your progress)
An iterate sequence satisfies x^{(k+1)}=0.2\,x^{(k)} with x^{(0)}=125. What is x^{(3)}?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
x^{(1)}=25, x^{(2)}=5, x^{(3)}=1 -- each step multiplies by 0.2.
Correct answer
Also accepted:
Why
If f(n)=O(n) and g(n)=O(n), what can you say about f(n)+g(n)?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Adding two linear-bounded quantities doesn't multiply their growth rate -- it stays linear, never jumping to quadratic.
O(1) means bounded by a constant -- adding two functions that can each grow like n can't collapse down to a constant bound.
The two individual big-O bounds are exactly enough information -- if f(n)\\le c_1n and g(n)\\le c_2n eventually, then f(n)+g(n)\\le(c_1+c_2)n eventually too.
Why
Big-O bounds add directly: if f(n)\le c_1n and g(n)\le c_2n for n past some threshold, then f(n)+g(n)\le(c_1+c_2)n, which is exactly the definition of O(n).
What is \displaystyle\lim_{k\to\infty}\left(4+\frac{6}{k}\right), where the vanishing term is added to a constant?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
As k\to\infty, 6/k\to0, leaving 4+0=4.
Correct answer
Also accepted:
Why
For f(n)=7n^2+3n, find the smallest integer constant c such that f(n)\le c\,n^2 holds for every n\ge1.
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
3n\le3n^2 for n\ge1, so f(n)=7n^2+3n\le7n^2+3n^2=10n^2. Checking c=9 fails at n=1: f(1)=10>9(1)^2=9. So c=10 is the smallest integer constant that works for every n\ge1.
Correct answer
Also accepted:
Why
What is \displaystyle\lim_{k\to\infty}\frac{3k^2+2k}{k^2-5}?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Divide numerator and denominator by k^2: \dfrac{3+2/k}{1-5/k^2}\to\dfrac{3+0}{1-0}=3.
Correct answer
Also accepted:
Why
Practice: Reading a limit and a big-$O$ bound together (3 problems · doesn’t affect your progress)
What is \displaystyle\lim_{k\to\infty}\left(7-\frac{3}{k^2}\right), where the vanishing term is subtracted and decays quadratically?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
As k\to\infty, 3/k^2\to0, leaving 7-0=7.
Correct answer
Also accepted:
Why
Is 5n\log n equal to O(n^2)?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
The opposite is true -- \\log n grows far SLOWER than n itself, not faster.
Big-O compares any two functions of n, products and pure powers alike.
Big-O's claim is about EVENTUAL behavior as n\\to\\infty, never restricted to small n.
Why
Since \log n=O(n), it follows that n\log n=O(n\cdot n)=O(n^2), so 5n\log n=O(n^2) too.
Yes -- \log n grows slower than any positive power of n, so 5n\log n is eventually beaten by a constant multiple of n^2
For f(n)=2n^2+9, find the smallest integer constant c such that f(n)\le c\,n^2 for every n\ge1.
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
At n=1: f(1)=11, requiring c\ge11; for n\ge1, 9\le9n^2, so f(n)\le2n^2+9n^2=11n^2 -- c=11 works for every n\ge1.
Correct answer
Also accepted:
Why