0 · Recall Warm-up
Answer from memory first. Answers are in the Answer Vault at the bottom.
- With a static variable inside a recursive function, why can’t you fill a table bottom-up? from Lesson 2.1.4
- How many calls does fib(5) make, and what is its recursion depth? from Lesson 2.1.2
- What is 1 + 2 + … + n? from Lesson 0.2.2
1 · The Hook
🎣
Two delivery apps find the nearest rider. One checks every pair of riders and customers; the other halves the search area each step. For 10 riders, both feel instant. For a million, one finishes before you blink and the other takes weeks. To choose between programs we need a short way to say how the work grows as the input grows, ignoring small details.
2 · Predict First
🤔
For n = 64, how many times does each counter grow?
int n = 64, i, j, a = 0, b = 0, c = 0;
for (i = 0; i < n; i++) a++;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) b++;
for (i = 1; i < n; i *= 2) c++;
printf("%d %d %d\n", a, b, c);
Make a guess in your head. The answer opens Section 3.
3 · Core Concept
💡
Predict First — the answer
Output
64 4096 6
One loop: n. Two nested loops: n² = 4096. A doubling counter: log₂ 64 = 6. As n grows, these three behave completely differently.
Counting basic steps
Pick a basic operation (a comparison, an addition, a loop body) and count how many times it runs as a function of the input size n. Lessons 1.2.2 and 0.2.2 did this exactly. For comparing programs, only the growth matters: constant factors and smaller terms are dropped.
Big-O
f(n) is O(g(n)) if, for large n, f(n) ≤ c·g(n) for some constant c: g is an upper bound on the growth. Examples: 3n + 5 is O(n); n(n + 1)/2 is O(n²); 7 is O(1). Two companions: Ω(g) means at least that growth (a lower bound), and Θ(g) means both (the exact growth rate).
Rules of thumb
- Drop constant factors: 5n² → n².
- Keep the dominant term: n² + 100n + 1000 → n².
- Sequential parts add: O(n) then O(n²) → O(n²).
- Nested loops multiply: n outer × n inner → O(n²); n outer × log n inner → O(n log n).
- A loop that halves or doubles its counter runs O(log n) times; the base of the log does not matter.
int n = 32, i, j, c = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j *= 2)
c++;
printf("%d\n", c);
Output
192
32 × 6 = 192 = n·(log₂ n + 1): O(n log n).
The growth ladder
| Order | Name | n = 10 | n = 1000 | n = 10⁶ | Typical source |
|---|---|---|---|---|---|
| O(1) | constant | 1 | 1 | 1 | one array access a[i] |
| O(log n) | logarithmic | ≈ 3.3 | ≈ 10 | ≈ 20 | halving: guessing game |
| O(n) | linear | 10 | 1000 | 10⁶ | one loop over the data |
| O(n log n) | linearithmic | ≈ 33 | ≈ 10⁴ | ≈ 2 × 10⁷ | n items × halving |
| O(n²) | quadratic | 100 | 10⁶ | 10¹² | two nested loops |
| O(2ⁿ) | exponential | 1024 | ≈ 10³⁰¹ | astronomical | naive recursive fib, Hanoi |
Recursion and Big-O
Count the calls and the work per call: factorial makes n calls with O(1) work each → O(n). Recursive fib makes about 2ⁿ calls (its exact count grows like 1.6ⁿ) → exponential. Hanoi makes 2ⁿ − 1 moves → O(2ⁿ). Power by halving → O(log n). Stack space grows with the recursion depth: factorial needs O(n) frames.
Best, worst and average case
Some programs do different amounts of work for different inputs of the same size: searching a list for a value may find it at the first position (best case) or not at all (worst case, n comparisons). Unless stated, “the complexity” means the worst case. This is a foundation only; the full theory belongs to the Algorithms subject. In PDS it is used to compare data-structure operations.
4 · Visual
Growth of work (each # ~ a fixed amount of work), n = 1, 2, 4, 8, 16:
n 1 2 4 8 16
log n # ## ### ####
n # ## #### ######## ################
n^2 # #### ###############...(256 for n = 16)
2^n ## #### ################ 65536 for n = 16
The ladder: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)
For large n the order of growth matters far more than any constant factor.
Slowest-growing on the left, fastest on the right.
5 · Worked Examples
Example 1 Easy
Give the Big-O of: (a) 4n + 9; (b) n²/2 + 3n; (c) 1000; (d) 2ⁿ + n³.
Solution
(a) O(n); (b) O(n²); (c) O(1); (d) O(2ⁿ) — the exponential dominates any power.
Example 2 Medium
What is the Big-O of for (i = 1; i <= n; i++) for (j = 1; j <= n; j *= 2) c++;? Check with n = 32.
Solution
The outer loop runs n times; the inner doubles j: ⌊log₂ n⌋ + 1 times. Total n(⌊log₂ n⌋ + 1) = 32 × 6 = 192 for n = 32 (computed above): O(n log n).
Example 3 GATE
Order these by growth for large n: n log n, 2ⁿ, n², log n, √n, n!, n.
Solution
log n < √n < n < n log n < n² < 2ⁿ < n!. (√n = n^0.5^ is between log n and n.)
6 · GATE Traps
⚠️
- Big-O is an upper bound: n is also O(n²), but Θ(n) is the tight answer GATE usually wants.
- Drop constants and lower terms only at the end; count the exact loop structure first.
- Logarithm bases do not change the order: log₂ n and log₁₀ n are both O(log n).
- Nested loops are not always O(n²): an inner loop that doubles is O(log n).
- Recursion: count calls × work per call; fib’s naive recursion is exponential.
8 · Memory Hook
🧠
“Only the fastest-growing term survives.” Constants are luggage; the dominant term is the vehicle.
9 · Connect the Dots
Phase 2 is complete: recursion and the language for counting work. Phase 3 begins with ways of organising data, and Big-O is how we will compare them. Next lesson answers: if we treat an array as a container of items, how much work do inserting, deleting and searching cost, and how is any element’s address found?
10 · Self-Test
GATE format. Try every question before opening the vault.
Q1MCQ1 markBig-O
3n² + 100n log n + 50 is:
- (A) O(n²)
- (B) O(n log n)
- (C) O(n³)
- (D) O(1)
Q2NAT2 marksSteps
What does this print?
int n = 32, i, j, c = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j *= 2)
c++;
printf("%d\n", c);
Numerical answer: ________
Q3MCQ1 markRecursion
The number of calls made by naive recursive fib(n) grows:
- (A) quadratically
- (B) linearly
- (C) exponentially
- (D) logarithmically
Q4MSQ1 markOrdering
Which statements are true for large n?
- (A) 2ⁿ grows slower than n¹⁰
- (B) n! grows faster than 2ⁿ
- (C) n log n grows slower than n²
- (D) log n grows slower than √n
Q5MCQ1 markLoop
What is the order of for (i = n; i > 1; i = i / 2) c++;?
- (A) O(1)
- (B) O(n)
- (C) O(n log n)
- (D) O(log n)
11 · Rule Card
- Count basic steps; keep the dominant term; drop constants.
- O = upper bound, Ω = lower bound, Θ = exact growth.
- Sequence adds; nesting multiplies; halving/doubling loop = O(log n).
- 1 log n √n n n log n n² n³ 2ⁿ n!
- Recursion: (number of calls) × (work per call); stack space = depth.
- Default = worst case.
12 · Concept Ledger
Unlocked in this lesson. From here on, these terms may be used.
Big-OΩΘdominant termO(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ)worst / best / average casecomplexity
13 · Answer Vault
Answer Vault
Try the questions first. Open when you are ready to check.
Recall Warm-up
- The static is shared by all calls, so each result depends on the order of calls; you must trace in execution order.
- 15 calls; depth 5.
- n(n + 1)/2.
Self-Test
Q1 Answer: (A)1 mark
n² dominates n log n.
- (B) is wrong: n² grows faster.
- (C) is wrong: An upper bound, but not tight; the dominant term is n².
- (D) is wrong: It grows with n.
Re-read: Lesson 2.2 — Counting work: a Big-O primer
Q2 Answer: 1922 marks
32 × 6 = 192.
Output
192
Re-read: Lesson 2.2 — Counting work: a Big-O primer
Q3 Answer: (C)1 mark
C(n) = 1 + C(n − 1) + C(n − 2).
- (A) is wrong: It outgrows any polynomial.
- (B) is wrong: fib(5) already makes 15 calls.
- (D) is wrong: It grows, not shrinks.
Re-read: Lesson 2.2 — Counting work: a Big-O primer
Q4 Answer: (B) (C) (D)1 mark
Exponentials outgrow every polynomial.
- (A) is wrong: 2ⁿ eventually exceeds n¹⁰.
Re-read: Lesson 2.2 — Counting work: a Big-O primer
Q5 Answer: (D)1 mark
i halves each time.
- (A) is wrong: It grows with n.
- (B) is wrong: It does not visit every value.
- (C) is wrong: Only one loop.
Re-read: Lesson 2.2 — Counting work: a Big-O primer