Phase 1 Checkpoint: 15 questions on asymptotic notation, loops and recurrences.
⏱️
15 questions · 24 marks · 40 minutes. Negative marking on MCQ only: −1/3 mark for a wrong 1-mark MCQ, −2/3 for a wrong 2-mark MCQ. No negative marking for MSQ or NAT; MSQ has no partial credit.
Q1MCQ1 markΘ
(2n + 1)(n + 3) is:
- (A) Θ(n log n)
- (B) Θ(n)
- (C) Θ(n²)
- (D) Θ(2ⁿ)
Q2MSQ2 marksO facts
Which are true?
- (A) n² = O(n² log n)
- (B) log(n¹⁰⁰) = Θ(log n)
- (C) 3ⁿ = O(2ⁿ)
- (D) 2ⁿ = O(n!)
Q3MCQ2 marksOrdering
Increasing order: f₁ = n log n, f₂ = n^(log log n), f₃ = n^(1.01), f₄ = 2^(√(log n)).
- (A) f₄, f₁, f₃, f₂
- (B) f₄, f₃, f₁, f₂
- (C) f₁, f₃, f₄, f₂
- (D) f₁, f₄, f₃, f₂
Q4MCQ1 markLimit
If f(n) = n log n and g(n) = n^1.5, then:
- (A) f = Ω(g)
- (B) f = Θ(g)
- (C) f = o(g)
- (D) f = ω(g)
Q5NAT2 marksExact loops
Exact count for n = 16?
for (i = 1; i <= n; i++)
for (j = i; j <= n; j++)
x++;
Numerical answer: ________
Q6MCQ1 markLoop growth
Θ of the count?
for (i = 1; i <= n; i++)
for (j = 1; j <= i * i; j++)
x++;
- (A) Θ(n²)
- (B) Θ(n² log n)
- (C) Θ(n³)
- (D) Θ(n⁴)
Q7NAT2 marksExact loops
Exact count for n = 64?
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j += i)
x++;
Numerical answer: ________
Q8NAT2 marksRecurrence
T(0) = 0, T(n) = 2T(n − 1) + 1. T(12) = ?
Numerical answer: ________
Q9NAT2 marksRecurrence
T(1) = 1, T(n) = 3T(n/2) + n (n a power of 2). T(8) = ?
Numerical answer: ________
Q10MCQ1 markRecursion tree
T(n) = T(n/3) + T(2n/3) + n is:
- (A) Θ(n)
- (B) Θ(n²)
- (C) Θ(n^(log 3))
- (D) Θ(n log n)
Q11MCQ1 markMaster
T(n) = 2T(n/2) + n² is:
- (A) Θ(n log n)
- (B) Θ(n)
- (C) Θ(n² log n)
- (D) Θ(n²)
Q12NAT2 marksMaster
T(n) = aT(n/2) + n² is Θ(n² log n). What is a?
Numerical answer: ________
Q13MCQ1 markRoots
T(n) = T(√n) + log n is:
- (A) Θ(log n)
- (B) Θ(√n)
- (C) Θ(log² n)
- (D) Θ(log log n)
Q14NAT2 marksDoubling array
A dynamic array starting at capacity 1 doubles when full. Total element copies during 70 appends?
Numerical answer: ________
Q15MSQ2 marksCases
Which are true?
- (A) Recursion depth contributes to space complexity.
- (B) Average case is always the mean of best and worst case.
- (C) Best case of linear search is 1 comparison.
- (D) An unsuccessful linear search over n elements makes n comparisons.
✓Answer Vault
Answer Vault
Try the questions first. Open when you are ready to check.
Q1 Answer: (C)1 mark
Product of two linear factors.
- (A) is wrong: No log.
- (B) is wrong: Too small.
- (D) is wrong: Not exponential.
Re-read: Lesson 1.1.1 — Big-O, Big-Ω and Θ: definitions with constants
Q2 Answer: (A) (B) (D)2 marks
3ⁿ/2ⁿ = 1.5ⁿ is unbounded.
- (C) is wrong: False.
Re-read: Lesson 1.1.1 — Big-O, Big-Ω and Θ: definitions with constants
Q3 Answer: (A)2 marks
Logs: f₄ = √(log n); f₁ ≈ log n; f₃ = 1.01 log n; f₂ = (log n)(log log n).
- (B) is wrong: n^1.01 eventually exceeds n log n.
- (C) is wrong: f₄ is the smallest.
- (D) is wrong: f₄ < n^ε for any ε, so below n log n.
Re-read: Lesson 1.1.2 — Little-o and little-ω; comparing and ordering functions
Q4 Answer: (C)1 mark
f/g = log n / √n → 0.
- (A) is wrong: f is smaller.
- (B) is wrong: Ratio is not constant.
- (D) is wrong: Reversed.
Re-read: Lesson 1.1.2 — Little-o and little-ω; comparing and ordering functions
Q5 Answer: 1362 marks
16 × 17 / 2.
Re-read: Lesson 1.1.3 — Analysing loops: nested, dependent and logarithmic loops
Q6 Answer: (C)1 mark
Σ i² = Θ(n³).
- (A) is wrong: Inner loop is quadratic in i.
- (B) is wrong: No log.
- (D) is wrong: Too large.
Re-read: Lesson 1.1.3 — Analysing loops: nested, dependent and logarithmic loops
Q7 Answer: 3372 marks
Σ ⌈64/i⌉ over i = 1..64.
Re-read: Lesson 1.1.3 — Analysing loops: nested, dependent and logarithmic loops
Q8 Answer: 40952 marks
2¹² − 1.
Re-read: Lesson 1.2.1 — Recurrences from recursive code; solving by unrolling (substitution)
Q9 Answer: 652 marks
T(2) = 5, T(4) = 19, T(8) = 65.
Re-read: Lesson 1.2.1 — Recurrences from recursive code; solving by unrolling (substitution)
Q10 Answer: (D)1 mark
Fractions sum to 1.
- (A) is wrong: Levels don't shrink.
- (B) is wrong: Too large.
- (C) is wrong: Not a master-form recurrence.
Re-read: Lesson 1.2.2 — The recursion-tree method
Q11 Answer: (D)1 mark
Case 3.
- (A) is wrong: f dominates.
- (B) is wrong: Too small.
- (C) is wrong: Not case 2.
Re-read: Lesson 1.2.3 — The master theorem
Q12 Answer: 42 marks
a = bᵈ = 2² gives case 2.
Re-read: Lesson 1.2.3 — The master theorem
Q13 Answer: (A)1 mark
S(m) = S(m/2) + m → Θ(m).
- (B) is wrong: Too large.
- (C) is wrong: Too large.
- (D) is wrong: That is T(√n) + 1.
Re-read: Lesson 1.2.4 — Harder recurrences: change of variables, T(n−1) forms, unequal splits
Q14 Answer: 1272 marks
Growths at sizes 1, 2, 4, 8, 16, 32, 64.
Re-read: Lesson 1.3.1 — Best, worst and average case; space complexity and recursion depth; amortised cost
Q15 Answer: (A) (C) (D)2 marks
Average case depends on the input distribution.
- (B) is wrong: Not in general.
Re-read: Lesson 1.3.1 — Best, worst and average case; space complexity and recursion depth; amortised cost