ACompressed recap
🧾
Count the basic steps as a function of n, then keep only the fastest-growing term without its constant. O bounds from above, Ω from below, Θ both. Sequential parts add, nested parts multiply, halving/doubling counters cost log n. The ladder: 1 < log n < √n < n < n log n < n² < 2ⁿ < n!. For recursion multiply calls by work per call; stack space follows the depth. Unless stated, use the worst case.
BMerged rule card
2.2 Counting work: a Big-O primer
- 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.
CInterleaved GATE-style questions
Q1MCQ1 markBig-O
n(n − 1)/2 comparisons are:
- (A) O(n)
- (B) O(n log n)
- (C) O(log n)
- (D) O(n²)
Q2NAT1 markSteps
A loop runs i = 1, 2, 4, … while i ≤ 1000. How many iterations?
Numerical answer: ________
Q3MCQ2 marksNested
What is the order of for (i = 0; i < n; i++) for (j = i; j < n; j++) c++;?
- (A) O(n log n)
- (B) O(n²)
- (C) O(2ⁿ)
- (D) O(n)
Q4MCQ1 markRecursion
The time of recursive factorial(n) (one call per level, O(1) work each) is:
- (A) O(n²)
- (B) O(log n)
- (C) O(1)
- (D) O(n)
Q5MSQ2 marksGrowth
Which functions are O(n²)?
- (A) 5n² + 3
- (B) n log n
- (C) n√n
- (D) 2ⁿ
Q6MCQ1 markLogs
Is log₁₀ n in O(log₂ n)?
- (A) No: base 10 is bigger
- (B) Only for n < 10
- (C) Only for powers of 2
- (D) Yes: logs of different bases differ by a constant factor
Q7NAT2 marksHanoi
Hanoi with n disks makes 2ⁿ − 1 moves. If one move takes a microsecond, about how many seconds does n = 20 take? (round to the nearest whole second)
Numerical answer: ________
Q8MCQ2 marksOrdering
Which is the correct increasing order?
- (A) log n, n, n log n, n²
- (B) n, log n, n log n, n²
- (C) log n, n log n, n, n²
- (D) n², n log n, n, log n
DAnswer Vault
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: (D)1 mark
n²/2 − n/2 → n².
- (A) is wrong: Quadratic, not linear.
- (B) is wrong: n² dominates.
- (C) is wrong: Far larger than log n.
Re-read: Lesson 2.2 — Counting work: a Big-O primer
Q2 Answer: 101 mark
⌊log₂ 1000⌋ + 1 = 10.
Re-read: Lesson 2.2 — Counting work: a Big-O primer
Q3 Answer: (B)2 marks
n + (n − 1) + … + 1 = n(n + 1)/2.
- (A) is wrong: The inner loop is linear.
- (C) is wrong: Polynomial, not exponential.
- (D) is wrong: The inner loop is not constant.
Re-read: Lesson 2.2 — Counting work: a Big-O primer
Q4 Answer: (D)1 mark
n calls.
- (A) is wrong: Only one call per level.
- (B) is wrong: n decreases by 1, not by half.
- (C) is wrong: Grows with n.
Re-read: Lesson 2.2 — Counting work: a Big-O primer
Q5 Answer: (A) (B) (C)2 marks
Big-O is an upper bound: anything growing no faster than n² qualifies; 2ⁿ grows faster.
- (D) is wrong: 2ⁿ outgrows n².
Re-read: Lesson 2.2 — Counting work: a Big-O primer
Q6 Answer: (D)1 mark
log₁₀ n = log₂ n / log₂ 10.
- (A) is wrong: Constant factors do not matter.
- (B) is wrong: True for all large n.
- (C) is wrong: True for all n.
Re-read: Lesson 2.2 — Counting work: a Big-O primer
Q7 Answer: 12 marks
2²⁰ − 1 ≈ 1.05 × 10⁶ μs ≈ 1 s.
Re-read: Lesson 2.2 — Counting work: a Big-O primer
Q8 Answer: (A)2 marks
log n < n < n log n < n².
- (B) is wrong: log n is smallest.
- (C) is wrong: n log n exceeds n.
- (D) is wrong: Reversed.
Re-read: Lesson 2.2 — Counting work: a Big-O primer