Asymptotic upper bound on algorithm complexity. O(1), O(n), O(n^2), O(log n).
Deep-dive lesson - accessible entry point but dense material. Use worked examples and spaced repetition.
When you pick an algorithm, you’re really picking a growth rate: how the time (or memory) cost scales as the input size n gets large. Big O is the compact language we use to talk about that growth—without getting distracted by machine speed, constant factors, or tiny lower-order details.
Big O notation, written O(g(n)), describes an asymptotic upper bound on how fast an algorithm’s resource usage can grow with input size n. It ignores constant factors and lower-order terms, keeping only the dominant growth rate (like O(1), O(log n), O(n), O(n²)). To use it, model the work as a function T(n) and keep the term that dominates as n → ∞.
If you time an algorithm on your laptop, the result depends on many accidental details:
But when we compare algorithms, we want something portable: a way to say “this will scale well” or “this will blow up” as the input size n grows.
That’s what Big O does. It describes asymptotic behavior: what happens as n → ∞.
Big O notation gives an asymptotic upper bound on a function’s growth.
If an algorithm takes time T(n), saying
T(n) ∈ O(g(n))
means: for sufficiently large n, T(n) grows no faster than a constant multiple of g(n).
We say f(n) ∈ O(g(n)) if there exist constants c > 0 and n₀ such that
∀ n ≥ n₀: 0 ≤ f(n) ≤ c · g(n)
Important parts to notice:
Big O is often used informally as “the runtime,” but technically:
So if someone says “this algorithm is O(n),” they mean “its runtime is in O(n)”—an upper bound.
Suppose an algorithm’s time is
T(n) = 3n² + 10n + 50
For small n, the +50 might matter. For large n, the 3n² dominates.
As n → ∞:
Big O intentionally ignores:
and keeps the dominant term: O(n²).
You can apply the same idea to:
Any resource that can be modeled as a function of input size n.
Think of g(n) as a ceiling shape. Saying f(n) ∈ O(g(n)) means that eventually, f(n) stays under some scaled version of that ceiling.
This is why Big O is an upper bound: it promises the function won’t grow faster than that ceiling (for large n).
When you run an algorithm, the exact time can vary by input. For example, searching an array:
Big O is commonly used to express worst-case asymptotic upper bounds, because worst-case gives a safety guarantee.
A common workflow:
If you have two loops each running about n times, the total iterations are about n · n = n², giving O(n²).
If you do 7 operations per element, you get T(n) = 7n, which is O(n).
Even though Big O doesn’t require calculus, your prerequisite knowledge of limits gives a clean intuition.
Consider f(n) = 3n² + 10n + 50 and g(n) = n².
Look at the ratio:
f(n) / g(n)
= (3n² + 10n + 50) / n²
= 3 + 10/n + 50/n²
Now take n → ∞:
limₙ→∞ (3 + 10/n + 50/n²)
= 3 + 0 + 0
= 3
So for large n, f(n) behaves like about 3 · n².
That implies f(n) ≤ c · n² for some constant c (for sufficiently large n), hence f(n) ∈ O(n²).
Here are the growth rates you’ll see constantly:
| Name | Big O | Typical pattern | Intuition |
|---|---|---|---|
| Constant | O(1) | fixed number of steps | doesn’t depend on n |
| Logarithmic | O(log n) | repeatedly halve / double | “how many times can I divide?” |
| Linear | O(n) | single pass | proportional to n |
| Linearithmic | O(n log n) | split + combine | common in efficient sorting |
| Quadratic | O(n²) | double nested loops | pairwise comparisons |
| Cubic | O(n³) | triple loops | many 3-way combinations |
| Exponential | O(2ⁿ) | branching recursion | doubles each step |
At difficulty 2, the “core” set is usually O(1), O(log n), O(n), O(n²).
Suppose n = 1,000,000.
The difference between O(n) and O(n²) is enormous at large n.
Big O can hide meaningful constants, especially for small n.
Example:
Big O says A is O(n) and B is O(n²), so A scales better.
But for n = 50:
So B is faster at n = 50, even though it scales worse.
That’s why Big O is about long-run scaling, not always about what is fastest for small inputs.
Let T(n) be a polynomial-like expression:
Because:
log_a n = (log_b n) / (log_b a)
and 1/(log_b a) is just a constant factor.
In real code, you rarely start with a clean formula. You start with loops, recursion, and data structure operations.
So the practical skill is: look at the shape of the code and map it to a growth rate.
Below are the most common patterns.
Typical examples (conceptually):
These do not scale with n.
Caveat: in real systems, some “simple” operations may hide complexity (like hash table worst-cases), but at this level we treat them as O(1) average-case.
Pattern:
If you do constant work each iteration, total work is proportional to n.
Pattern:
Total iterations: n · n = n².
A common variant is when the inner loop depends on i:
Total iterations:
∑ᵢ₌₁ⁿ i
= n(n + 1)/2
= (n² + n)/2
Now simplify to Big O:
(n² + n)/2 ∈ O(n²)
because the n² term dominates and 1/2 is a constant.
Pattern:
How many times can you halve n before it becomes 1?
If you halve k times:
n / 2ᵏ = 1
⇒ 2ᵏ = n
⇒ k = log₂ n
So the loop runs O(log n) times.
This is the key intuition behind binary search.
Two common sources:
1) A loop of n iterations, each doing O(log n) work (like inserting into a balanced tree):
T(n) = n · log n
2) Divide-and-conquer algorithms that split the problem and combine results efficiently.
Classic example: mergesort has runtime O(n log n).
When you see pieces of code one after another:
their costs add:
T(n) = T_A(n) + T_B(n)
Big O becomes dominated by the larger term.
When one piece is inside another (nested):
their costs multiply:
T(n) = T_outer(n) · T_inner(n)
Big O is most often used for worst-case.
But you’ll also see:
A helpful table:
| Case | Meaning | Why you care |
|---|---|---|
| Best-case | minimum work | optimistic, often not guaranteed |
| Average-case | expected work | realistic if assumptions hold |
| Worst-case | maximum work | guarantees performance ceiling |
An algorithm can be fast but memory-hungry or vice versa.
Examples:
You should always ask: “What resource are we bounding?”
Time: T(n) ∈ O(g(n))
Space: S(n) ∈ O(h(n))
Same notation, different resource.
Big O is the difference between:
Quadratic algorithms (O(n²)) are often fine for n ≈ 10³ to 10⁴, but become painful past that. Linearithmic (O(n log n)) scales to much larger n.
Here are common tasks and what Big O suggests.
| Task | Naive approach | Big O | Better approach | Big O |
|---|---|---|---|---|
| Find an element in unsorted array | scan | O(n) | (can’t asymptotically beat without assumptions) | O(n) |
| Find in sorted array | scan | O(n) | binary search | O(log n) |
| Sort numbers | bubble/selection | O(n²) | mergesort/heapsort | O(n log n) |
| Check duplicates | compare all pairs | O(n²) | hash set | O(n) average |
Big O doesn’t tell you everything, but it quickly eliminates bad options at scale.
This node unlocks several big ideas because Big O is the entry point to complexity theory and algorithm design.
When you claim an algorithm is O(n log n), you’re making a promise:
This is why careful definitions matter: they let you prove performance properties independent of hardware.
Choosing n is part of the modeling step:
You’ll later see multi-parameter Big O like O(n + m). For now, focus on single-parameter n to build solid intuition.
Big O is a zoomed-out view. Zoom out far enough (n large), and only the overall shape matters:
Learning to see that shape in code is one of the highest-leverage skills in algorithms.
An algorithm has runtime T(n) = 12n + 3n² + 100. Find its Big O class using dominant-term reasoning.
Start with the runtime function:
T(n) = 12n + 3n² + 100
Reorder by degree (highest power first):
T(n) = 3n² + 12n + 100
Identify the dominant term as n → ∞:
Drop lower-order terms and constant factors:
T(n) ∈ O(n²)
Insight: Big O keeps the growth rate that dominates for large n. Any polynomial is dominated by its highest-degree term.
Consider code where i runs from 1 to n, and for each i, j runs from 1 to i. Assume the inner loop body is O(1). Compute T(n) and simplify to Big O.
Total work equals the total number of inner-loop iterations:
T(n) = ∑ᵢ₌₁ⁿ i
Use the closed form for the sum of the first n integers:
∑ᵢ₌₁ⁿ i = n(n + 1)/2
Expand:
T(n) = (n² + n)/2
Simplify to Big O by dropping constants and lower-order terms:
(n² + n)/2 ∈ O(n²)
Insight: Not all nested loops are exactly n² iterations. Summations help you count precisely; Big O then compresses the result.
A loop repeatedly halves n until it reaches 1: while n > 1: n = n/2. How many iterations does it run?
After k iterations, n becomes:
n / 2ᵏ
Stop condition is when this is ≤ 1:
n / 2ᵏ ≤ 1
Solve for k:
n ≤ 2ᵏ
⇒ log₂ n ≤ k
So k grows proportionally to log n:
iterations ∈ O(log n)
Insight: Logarithms appear when you repeatedly multiply/divide by a constant factor (like halving).
Big O, written O(g(n)), is an asymptotic upper bound: for large n, f(n) ≤ c · g(n) for some constants c, n₀.
Big O focuses on growth as n → ∞, ignoring constant factors and lower-order terms.
Common growth rates: O(1), O(log n), O(n), O(n log n), O(n²).
Sequential parts add (T = A + B), nested parts multiply (T = A · B).
O(log n) often comes from repeated halving/doubling; O(n²) often comes from comparing all pairs.
Big O can describe time or space; always state which resource you mean.
Big O is usually a worst-case upper bound, providing a performance guarantee ceiling.
Thinking O(n) means “exactly n steps.” It means “at most proportional to n” for sufficiently large n (up to constants).
Forgetting the difference between sequential vs nested code when combining costs (adding when you should multiply, or vice versa).
Treating Big O as a precise benchmark for small n; constants can dominate at small sizes.
Assuming every nested loop is O(n²); many are triangular (∑ i) or depend on changing bounds. Count carefully.
Simplify T(n) = 5n³ + 20n² + 7 to Big O.
Hint: Which term dominates as n → ∞? Drop constants and lower powers.
The dominant term is 5n³. Dropping constants and lower-order terms gives T(n) ∈ O(n³).
A loop runs i from 1 to n. Inside it, a loop runs j from 1 to 100. The body is O(1). What is the total time complexity in Big O?
Hint: The inner loop bound is constant with respect to n.
Inner loop does 100 iterations → O(1) per outer iteration. Total T(n) = n · 100 ∈ O(n).
You have an array of length n that is already sorted. You want to check whether a value x is present. Compare the Big O of (1) scanning from start to end and (2) binary search.
Hint: Scanning checks items one by one; binary search halves the search interval each step.
Scan: O(n). Binary search: O(log n) because each comparison halves the remaining range.
Up next, Big O becomes the backbone for nearly every algorithms topic: