Recurrence Relations Practice Questions

### 1. Fundamental Definitions and Classification In the domain of GATE CSE, recurrence relations serve as the definitive mathematical tool for quantifying the asymptotic behavior of recursive algorithms. To analyze any recursive procedure, we must bridge the gap between code logic and mathematical modeling by defining the total work $T(n)$ in terms of smaller instances of the same problem. A recurrence relation is an equation that expresses a sequence term as a function of its preceding terms. For these models to be computationally valid, they must include a base condition—a constant-time termination point (e.g., $T(1) = \Theta(1)$) that prevents infinite recursion. **Classification Matrix:** | Category | Logic | Example | | :--- | :--- | :--- | | **Divide-and-Conquer** | Problem split into $a$ subproblems of size $n/b$. | $T(n) = 2T(n/2) + n$ | | **Linear/Decremental** | Size reduces by a constant amount (e.g., $n-1$). | $T(n) = T(n-1) + n$ | | **Homogeneous** | The difference between terms equals zero. | $a_n - 3a_{n-1} = 0$ | | **Non-Homogeneous** | The difference between terms is a function $f(n) \neq 0$. | $a_n - 2a_{n-1} = 3^n$ | ### 2. Core Idea: From Recursion to Mathematical Representation Recursive decomposition is a strategic design choice where a complex problem is reduced to subproblems of the same type. The total time complexity $T(n)$ is the sum of the time spent in recursive calls and the work required for the "divide and combine" steps, denoted as $f(n)$. Mathematically, this is represented as $T(n) = aT(n/b) + f(n)$. Here, $a$ represents the branching factor (number of recursive calls), and $n/b$ represents the reduced input size. A recursion tree provides a visual trace of this flow, where each node captures the cost $f(n)$ at that specific level of recursion. Understanding this structural growth is paramount to identifying whether an algorithm will scale linearly, logarithmically, or exponentially. ### 3. Key Properties for GATE Analysis Identifying structural properties allows a candidate to apply rapid elimination strategies in Multiple Select Questions (MSQs). As a technical architect, you must evaluate the following: - **Branching Factor ($a$)**: Dictates the tree's width. If $a > 1$, the tree expands, potentially leading to polynomial or exponential complexity. - **Base Case Necessity**: Any recurrence without a valid base case is mathematically divergent and computationally invalid. - **Work per Level ($f(n)$)**: If $f(n)$ grows faster than the number of leaves, the root dominates. If the leaves grow faster, the complexity is $\Theta(n^{\log_b a})$. > **Senior Educator’s Strategy**: Immediately discard options where the branching factor $a$ implies exponential growth (e.g., $a=2, b=1$) but the proposed complexity is polynomial. Conversely, for divide-and-conquer, if $f(n)$ is a lower-order polynomial than the leaf count, the leaves always dictate the bound. ### 4. Formalizing Recurrence Relations from Algorithms Correct formulation is the prerequisite for any solution. A common pitfall is neglecting the $f(n)$ cost, such as the linear-time "Merge" step in Merge Sort. **Step-by-Step Derivation: Merge Sort** - **Divide**: Splitting the array takes $\Theta(1)$. - **Recurse**: The algorithm calls itself twice on halves of the input $\rightarrow 2T(n/2)$. - **Combine**: The Merge procedure compares $n$ elements $\rightarrow \Theta(n)$. - **Result**: $T(n) = 2T(n/2) + \Theta(n)$. **Classic Algorithm Formulations:** | Algorithm | Recurrence Relation | Result | | :--- | :--- | :--- | | **Binary Search** | $T(n) = T(n/2) + \Theta(1)$ | $\Theta(\log n)$ | | **Merge Sort** | $T(n) = 2T(n/2) + \Theta(n)$ | $\Theta(n \log n)$ | | **Tower of Hanoi** | $T(n) = 2T(n-1) + \Theta(1)$ | $\Theta(2^n)$ | | **Quick Sort (Worst)** | $T(n) = T(n-1) + \Theta(n)$ | $\Theta(n^2)$ | ### 5. The Substitution Method (Guess-and-Prove) The substitution method is the rigorous standard for formal proofs. It utilizes mathematical induction to verify an asymptotic "guess." Derivation for $T(n) = 2T(n/2) + n$ to prove $O(n \log n)$: - **Guess**: $T(n) \le cn \log n$. - **Assumption**: Assume true for $n/2$, i.e., $T(n/2) \le c(n/2) \log(n/2)$. - **Substitution**: $$T(n) = 2T(n/2) + n \le 2[c(n/2) \log(n/2)] + n$$ $$T(n) \le cn (\log n - \log 2) + n \le cn \log n - cn + n$$ - **Verification**: For $c \ge 1$, $T(n) \le cn \log n$. The proof holds. **Method Properties:** - **Pros**: High precision; solves non-standard forms. - **Cons**: Requires a correct initial guess; algebraically intensive. ### 6. Iteration and Expansion Method This method "unrolls" the recurrence to reveal a summation pattern, ideal for linear recurrences where the reduction is additive. *Example*: $T(n) = T(n-1) + n$ with $T(0) = 0$ $$T(n) = [T(n-2) + (n-1)] + n$$ $$T(n) = [T(n-3) + (n-2) + (n-1)] + n$$ - **General Form**: $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ - **Complexity**: $\Theta(n^2)$ ### 7. The Recursion Tree Method The recursion tree is the visual bridge for unbalanced or multi-term recurrences. - **Unbalanced Tree Height**: For $T(n) = T(n/4) + T(n/2) + cn^2$, the branches have different lengths. The longest path to a leaf is $\log_2 n$ (via the $n/2$ branch). - **Total Cost**: Summing work per level gives $cn^2(1 + 5/16 + 25/256 + \dots)$. Since the ratio $r = 5/16 < 1$, the geometric series converges, meaning the root dominates. Thus, $T(n) = \Theta(n^2)$. ### 8. Master Theorem: Standard and Advanced Versions The Master Theorem is the primary shortcut for $T(n) = aT(n/b) + \Theta(n^k \log^p n)$. **Master Theorem Case Summary:** | Compare $a$ with $b^k$ | Condition | Resulting $\Theta(n)$ | | :--- | :--- | :--- | | $a > b^k$ | Root work is less than leaf work | $\Theta(n^{\log_b a})$ | | $a = b^k$ | Work is balanced | (a) $p > -1$: $\Theta(n^k \log^{p+1} n)$ <br> (b) $p = -1$: $\Theta(n^k \log \log n)$ <br> (c) $p < -1$: $\Theta(n^k)$ | | $a < b^k$ | Root work dominates | (a) $p \ge 0$: $\Theta(n^k \log^p n)$ <br> (b) $p < 0$: $\Theta(n^k)$ | > **Note**: If $f(n)$ is not polynomial (e.g., $2^n$), Master Theorem fails. ### 9. Advanced Recurrence Concepts (Rank-Breakers) **Variable Transformation:** For $T(n) = \sqrt{n}T(\sqrt{n}) + n$ (GATE 2024): - Divide by $n$: $\frac{T(n)}{n} = \frac{T(\sqrt{n})}{\sqrt{n}} + 1$. - Let $S(n) = \frac{T(n)}{n}$, so $S(n) = S(\sqrt{n}) + 1$. - Let $n = 2^m$: $S(2^m) = S(2^{m/2}) + 1$. Let $G(m) = S(2^m) \implies G(m) = G(m/2) + 1$. - By Master Theorem, $G(m) = \Theta(\log m)$. - Substitute back: $m = \log n \implies S(n) = \Theta(\log \log n)$. - Finally, $T(n) = n \cdot S(n) = \Theta(n \log \log n)$. **Generating Functions (6-Step Procedure):** Used for recurrences like Fibonacci ($a_n = a_{n-1} + a_{n-2}$): 1. Rewrite the relation as an equation (e.g., $a_n - a_{n-1} - a_{n-2} = 0$). 2. Multiply by $x^n$ and sum from $n=2$ to $\infty$. 3. Define $G(x) = \sum_{n=0}^{\infty} a_n x^n$ and substitute into the equation to find $G(x)$ in terms of $x$. 4. Decompose $G(x)$ using partial fractions (for Fibonacci, roots are $\frac{1 \pm \sqrt{5}}{2}$). 5. Express $G(x)$ as a sum of geometric series. 6. Extract $a_n$ as the coefficient of $x^n$. ### 10. Complexity Analysis and Recursive Stack Recursive algorithms incur overhead in the System Stack. | Algorithm | Time | Space (Stack) | | :--- | :--- | :--- | | **Binary Search** | $\Theta(\log n)$ | $\Theta(\log n)$ | | **Merge Sort** | $\Theta(n \log n)$ | $\Theta(n)$ | | **Quick Sort** | Avg: $\Theta(n \log n)$, Worst: $\Theta(n^2)$ | Avg: $\Theta(\log n)$, Worst: $\Theta(n)$ | ### 11. Classic GATE Problem Case Studies - **GATE 2025**: $T(n) = 2T(n-1) + n 2^n \implies \text{Solution}: \Theta(n^2 2^n)$. - **GATE 2026 (Expected Pattern)**: $T_1(n) = 4T_1(n/2) + T_2(n)$ where $T_2(n) = \Theta(n^{\log_4 5}) \implies \text{Result}: \Theta(n^{\log_4 5})$. - **Karatsuba Multiplication**: $T(n) = 3T(n/2) + \Theta(n) \rightarrow \Theta(n^{\log_2 3}) \approx \Theta(n^{1.58})$. ### 12. Common GATE PYQ Patterns and Traps - **Non-Polynomial $f(n)$ Trap**: $T(n) = 2T(n/2) + 2^n$. Master Theorem is inapplicable here because $f(n)$ must be polynomial relative to $n^{\log_b a}$. Use the Iteration Method. - **MSQ Trap**: $T(n) = 2T(n/2) + \log n$. Students often pick $\Theta(\log n)$ or $\Theta(n \log n)$. Correct answer: $a=2, b=2, k=0 \rightarrow a > b^k$ (Case 1) $\implies \text{Result}: \Theta(n)$. - **Variable Trap**: In $T(n) = 2T(n/2) + n/ \log n$, Master Theorem fails (Case 2 gap). ### 13. Fast Revision Notes & Shortcut Cheat Sheet **Strategy Flowchart:** - Form: $aT(n/b) + f(n)$? $\rightarrow$ Yes: Use Master Theorem. - Non-standard (roots/exponents)? $\rightarrow$ Yes: Substitute $n = 2^m$. - Linear ($n-1, n-2$)? $\rightarrow$ Yes: Iteration or Characteristic Equation. - Unbalanced/Complex? $\rightarrow$ Yes: Draw Recursion Tree. **High-Frequency Formulas:** - **Arithmetic**: $\sum i = \Theta(n^2)$ - **Geometric ($r < 1$)**: Sum is $\Theta(\text{First Term})$ - **Geometric ($r > 1$)**: Sum is $\Theta(\text{Last Term})$ **48-Hour Priority List:** - Master Theorem Case 2 variations ($p = -1$, $p < -1$). - Variable substitution for $T(\sqrt{n})$ and $T(n) = \sqrt{n}T(\sqrt{n}) + n$. - Recursion stack depth for Worst-Case Quick Sort ($\Theta(n)$). - Generating function 6-step procedure for linear homogeneous recurrences.