Level 1 — RecognitionComplexity Analysis

Complexity Analysis

⏱ 20 minutes30 marksprintable — key stays hidden on paper

Chapter: 3.1 Complexity Analysis Level: 1 — Recognition (MCQ + Matching + True/False with justification) Time limit: 20 minutes Total marks: 30

Section A — Multiple Choice (1 mark each)

Choose the single best answer.

Q1. By the formal definition, $f(n) = O(g(n))$ means there exist constants $c > 0$ and $n_0 > 0$ such that for all $n \ge n_0$ :

(a) $f(n) \ge c \cdot g(n)$
(b) $f(n) \le c \cdot g(n)$
(c) $f(n) = c \cdot g(n)$
(d) $c \cdot g(n) \le f(n) \le c \cdot g(n)$

Q2. Which complexity grows the fastest as $n \to \infty$ ?

(a) $O(n^3)$
(b) $O(2^n)$
(c) $O(n!)$
(d) $O(n \log n)$

Q3. Binary search on a sorted array of $n$ elements has worst-case time complexity:

(a) $O(1)$
(b) $O(\log n)$
(c) $O(n)$
(d) $O(n \log n)$

Q4. The Master Theorem for $T(n) = a\,T(n/b) + f(n)$ compares $f(n)$ against:

(a) $n^{a/b}$
(b) $n^{\log_b a}$
(c) $a \cdot n^b$
(d) $b^{\log_a n}$

Q5. Auxiliary space complexity refers to:

(a) total memory including the input
(b) extra space used excluding the input
(c) only the space used by recursion
(d) space measured in bits, not bytes

Q6. For the recurrence $T(n) = 2T(n/2) + n$ , the solution is:

(a) $\Theta(n)$
(b) $\Theta(n^2)$
(c) $\Theta(n \log n)$
(d) $\Theta(\log n)$

Q7. Amortized analysis is used to:

(a) find the exact worst case of a single operation
(b) average the cost over a sequence of operations
(c) measure only the best-case cost
(d) compute space rather than time

Q8. $\Theta(g(n))$ provides a:

(a) tight bound (both upper and lower)
(b) upper bound only
(c) lower bound only
(d) average-case bound only

Q9. Linear search's best case (target is first element) is:

(a) $O(n)$
(b) $O(\log n)$
(c) $O(1)$
(d) $O(n^2)$

Q10. The dynamic-array (doubling) push operation has amortized time per push of:

(a) $O(n)$
(b) $O(\log n)$
(c) $O(1)$
(d) $O(n \log n)$

Section B — Matching (1 mark each, 6 marks)

Q11. Match each algorithm/scenario (left) to its typical time complexity (right).

#	Item		Complexity
i	Accessing array element by index	A	$O(n^2)$
ii	Merge sort	B	$O(1)$
iii	Naïve nested-loop bubble sort	C	$O(2^n)$
iv	Generating all subsets of a set	D	$O(n \log n)$
v	Traversing a linked list once	E	$O(n!)$
vi	Brute-force travelling salesman (all permutations)	F	$O(n)$

Write pairs, e.g. i–B.

Section C — True/False WITH Justification (2 marks each: 1 verdict + 1 justification)

Q12. $5n^2 + 3n = O(n^2)$ . (T/F + justify)

Q13. If $f(n) = \Theta(g(n))$ then $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$ . (T/F + justify)

Q14. $O(n \log n)$ is asymptotically worse than $O(n^2)$ . (T/F + justify)

Q15. The recurrence $T(n) = T(n-1) + O(1)$ solves to $\Theta(\log n)$ . (T/F + justify)

Q16. In quicksort, the worst case ( $O(n^2)$ ) and average case ( $O(n\log n)$ ) differ; therefore Big-O of the worst case is $O(n\log n)$ . (T/F + justify)

Q17. In the Master Theorem, if $f(n) = \Theta(n^{\log_b a})$ , then $T(n) = \Theta(n^{\log_b a}\log n)$ . (T/F + justify)

Q18. An algorithm that uses $O(1)$ auxiliary space always uses $O(1)$ total space. (T/F + justify)

Answer keyMark scheme & solutions

Section A (10 marks)

Q1 — (b) $f(n) \le c\,g(n)$ for all $n \ge n_0$ . Big-O is an upper bound. (1)

Q2 — (c) $O(n!)$ . Growth order: $n\log n < n^3 < 2^n < n!$ . Factorial dominates exponential (Stirling: $n! \sim \sqrt{2\pi n}(n/e)^n$ beats $2^n$ ). (1)

Q3 — (b) $O(\log n)$ — each step halves the search interval. (1)

Q4 — (b) $n^{\log_b a}$ — the "watershed" function of the Master Theorem. (1)

Q5 — (b) Extra space excluding input. Total = input + auxiliary. (1)

Q6 — (c) $\Theta(n\log n)$ . Here $a=2,b=2,f(n)=n$ ; $n^{\log_2 2}=n$ , so Case 2 gives $\Theta(n\log n)$ . (1)

Q7 — (b) Averages cost across a sequence of operations (worst-case average). (1)

Q8 — (a) Tight bound: $c_1 g \le f \le c_2 g$ . (1)

Q9 — (c) $O(1)$ — found on first comparison. (1)

Q10 — (c) $O(1)$ amortized (doubling spreads resize cost). (1)

Section B (6 marks)

Q11.

i–B ( $O(1)$ index access)
ii–D (merge sort $O(n\log n)$ )
iii–A (bubble sort $O(n^2)$ )
iv–C (subsets: $2^n$ )
v–F (linked-list traversal $O(n)$ )
vi–E (all permutations $O(n!)$ )

1 mark each correct pair.

Section C (14 marks)

Q12 — TRUE. (1) Justification: choose $c=8, n_0=1$ ; then $5n^2+3n \le 8n^2$ for all $n\ge1$ . Lower-order term $3n$ is dominated. (1)

Q13 — TRUE. (1) $\Theta$ is defined exactly as the intersection of $O$ (upper) and $\Omega$ (lower); by definition it implies both. (1)

Q14 — FALSE. (1) $O(n\log n)$ grows slower than $O(n^2)$ (since $\log n < n$ ), so it is better, not worse. (1)

Q15 — FALSE. (1) Unrolling gives $T(n)=T(0)+n\cdot O(1)=\Theta(n)$ , a linear sum, not logarithmic. (1)

Q16 — FALSE. (1) The worst case is $O(n^2)$ ; you cannot bound the worst case by $O(n\log n)$ . Best/average/worst are separate cases each with their own bound. (1)

Q17 — TRUE. (1) This is Master Theorem Case 2: when $f(n)=\Theta(n^{\log_b a})$ , we get $T(n)=\Theta(n^{\log_b a}\log n)$ . (1)

Q18 — FALSE. (1) Total space always includes the input, which is $\Omega(n)$ for an input of size $n$ ; so total space is $\ge O(n)$ even when auxiliary is $O(1)$ . (1)

[
  {"claim":"Q6/Q17: T(n)=2T(n/2)+n gives Theta(n log n) via Master Case 2 since n^{log_2 2}=n",
   "code":"a=2; b=2; e=Rational(a).__class__; import sympy; logba=sympy.log(a,b); result=(sympy.simplify(logba-1)==0)"},
  {"claim":"Q2: n! eventually exceeds 2^n for n>=4",
   "code":"n=sympy.symbols('n'); vals=[sympy.factorial(k) > 2**k for k in range(4,10)]; result=all(bool(v) for v in vals)"},
  {"claim":"Q12: 5n^2+3n <= 8n^2 for all n>=1",
   "code":"n=sympy.symbols('n', positive=True); diff=8*n**2-(5*n**2+3*n); checks=[diff.subs(n,k)>=0 for k in range(1,20)]; result=all(bool(c) for c in checks)"},
  {"claim":"Q14: for n>=2, n*log(n) < n^2 (n log n asymptotically smaller)",
   "code":"import math; checks=[k*math.log(k) < k*k for k in range(2,50)]; result=all(checks)"}
]