The Exam Blueprint: Module 1 PYQ Deep Analysis (2022–2024)

An analysis of 20 exam questions spanning 2022 to 2024 reveals that Module 1 is foundational and predictable. Master's Theorem and the Substitution Method are guaranteed to appear every single year for 5–7 marks each. The theoretical aspect strictly focuses on Asymptotic Notations and Time/Space Complexity definitions.

Complete PYQ Table (20 Questions)

Total marks tracked: 108 marks across 3 years.

---

Topic Heat Map

---

The 3 Guaranteed Question Types

1. 🔴 Substitution Method Recurrence (7M) — appeared in ALL 3 years Always a different form. You must show the expansion steps clearly, generalize to the $k$-th step, and substitute the base case. Examples: $3f(n/2)+6$, $2T(n/2)+n$, $T(n-1)+n$.

2. 🔴 Master's Theorem Application (5–7M) — appeared in ALL 3 years You must state the values of $a$, $b$, and $f(n)$, calculate $n^{\log_b a}$, and explicitly state which Case applies. Watch out for equations where the theorem fails (like $T(n) = 2T(n/2) + n/\log n$).

3. 🟠 Asymptotic Notation Theory (7M) — appeared in ALL 3 years Either "explain O/Ω/Θ" or "differentiate best/worst/average cases." Always include graphs and a standard example (like Linear Search) in your answers.

Solved Numericals: The Exam-Critical Calculations

---

Numerical 1: Substitution Method

"T(n) = T(n−1) + n, with T(1) = 1. Solve using substitution method."

Step 1: Expand the recurrence $T(n) = T(n-1) + n$ $T(n-1) = T(n-2) + (n-1)$ $T(n-2) = T(n-3) + (n-2)$

Step 2: Substitute back $T(n) = [T(n-2) + (n-1)] + n$ $T(n) = [T(n-3) + (n-2)] + (n-1) + n$

Step 3: Generalize for k steps $T(n) = T(n-k) + (n-(k-1)) + \dots + (n-1) + n$

Step 4: Reach the base case We reach the base case when $n-k = 1 \implies k = n-1$. $T(n) = T(1) + 2 + 3 + \dots + (n-1) + n$ $T(n) = 1 + 2 + 3 + \dots + n$

Step 5: Solve This is the sum of the first $n$ natural numbers. $T(n) = \frac{n(n+1)}{2} = \frac{n^2}{2} + \frac{n}{2}$ Complexity: $O(n^2)$

---

Numerical 2: Master's Theorem Cases

"Use Master's Theorem to solve: (i) T(n) = 2T(n/2) + n, (ii) T(n) = 3T(n/2) + n², (iii) T(n) = 2T(n/2) + n/log n. Explain which case applies."

(i) $T(n) = 2T(n/2) + n$

• $a=2, b=2, f(n)=n$
• $n^{\log_b a} = n^{\log_2 2} = n^1 = n$
• Since $f(n) = \Theta(n^{\log_b a})$, Case 2 applies.
• Solution: $T(n) = \Theta(n \log n)$

(ii) $T(n) = 3T(n/2) + n^2$

• $a=3, b=2, f(n)=n^2$
• $n^{\log_b a} = n^{\log_2 3} \approx n^{1.58}$
• Since $f(n) = \Omega(n^{\log_b a + \epsilon})$ for $\epsilon \approx 0.4$, we check the regularity condition: $3(n/2)^2 \le c n^2 \implies \frac{3}{4} n^2 \le c n^2$ (holds for $c \ge 3/4$).
• Case 3 applies.
• Solution: $T(n) = \Theta(n^2)$

(iii) $T(n) = 2T(n/2) + n/\log n$

• $a=2, b=2, f(n) = n/\log n$
• $n^{\log_b a} = n^{\log_2 2} = n$
• We compare $f(n) = n/\log n$ with $n$. Here, $f(n)$ is asymptotically smaller than $n$, but NOT polynomially smaller (the ratio is $\log n$, not $n^\epsilon$).
• Master's Theorem DOES NOT APPLY (it falls into the gap between Case 1 and Case 2).

---

Numerical 3: The Variable Substitution Trap

"Find time complexity: T(n) = 2T(n^(1/2)) + log n"

This cannot be solved directly by Master's Theorem. We must transform it. Let $n = 2^m \implies m = \log_2 n$. Substitute $n$: $T(2^m) = 2T(2^{m/2}) + m$

Now, rename the function to make it look standard: Let $S(m) = T(2^m)$. $S(m) = 2S(m/2) + m$

Now apply Master's Theorem to $S(m)$:

• $a=2, b=2, f(m)=m$
• $m^{\log_2 2} = m$
• $f(m) = \Theta(m)$, so Case 2 applies.
• Solution for $S(m)$: $S(m) = \Theta(m \log m)$

Substitute back $m = \log n$: $T(n) = \Theta(\log n \cdot \log(\log n))$

High-Yield Subjective Bank: Structure Your Answers

---

####Explain Asymptotic Notations (7 Marks)**

Answer structure:

1. Definition (1M): Asymptotic notations are mathematical tools used to represent the time and space complexity of algorithms as input size $n \to \infty$.
2. Big-O (O) Notation - Upper Bound (2M):
   • Represents the worst-case scenario.
   • $f(n) = O(g(n))$ if there exist constants $c > 0$ and $n_0 \ge 0$ such that $0 \le f(n) \le c \cdot g(n)$ for all $n \ge n_0$.
   • Draw a graph showing $c \cdot g(n)$ staying above $f(n)$ after $n_0$.
3. Big-Omega (Ω) Notation - Lower Bound (2M):
   • Represents the best-case scenario.
   • $f(n) = \Omega(g(n))$ if there exist constants $c > 0$ and $n_0 \ge 0$ such that $0 \le c \cdot g(n) \le f(n)$ for all $n \ge n_0$.
   • Draw a graph showing $c \cdot g(n)$ staying below $f(n)$ after $n_0$.
4. Big-Theta (Θ) Notation - Tight Bound (2M):
   • Represents the exact bound (average case).
   • $f(n) = \Theta(g(n))$ if there exist constants $c_1, c_2 > 0$ and $n_0 \ge 0$ such that $0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$ for all $n \ge n_0$.
   • Draw a graph showing $f(n)$ sandwiched between $c_1g(n)$ and $c_2g(n)$.

---

Differentiate Best, Worst, Average Case + Why Worst is Preferred (7 Marks)**

Answer structure:

1. Best Case (1.5M): Minimum time required for program execution. For Linear Search on array $A$, the target is at $A[0]$. Complexity: $\Omega(1)$. Not very useful for practical guarantees.
2. Worst Case (1.5M): Maximum time required. Target is at the very end or not in the array at all. The algorithm must check all $n$ elements. Complexity: $O(n)$.
3. Average Case (1.5M): Expected time over all possible inputs. For Linear Search, target is somewhere in the middle (expected checks = $n/2$). Complexity: $\Theta(n)$.
4. Why Worst-Case is Preferred (2.5M):
   • It provides an absolute guarantee — the algorithm will never take longer than this.
   • Crucial for real-time systems (e.g., medical devices, avionics) where missing a deadline causes failure.
   • Average-case is often mathematically difficult to compute and depends on assumptions about input probability distributions that might not hold true in reality.