Recurrence Relations – GATE CSE AlgorithmsPractice Questions & PYQs

Divide the recurrence $T(n) = \sqrt{2} T(n/2) + \sqrt{n}$ by $\sqrt{n}$ to obtain $\frac{T(n)}{\sqrt{n}} = \frac{\sqrt{2} T(n/2)}{\sqrt{n}} + 1$.
Since $\sqrt{n} = \sqrt{2} \sqrt{n/2}$, this simplifies to $\frac{T(n)}{\sqrt{n}} = \frac{T(n/2)}{\sqrt{n/2}} + 1$.
By substituting $S(n) = \frac{T(n)}{\sqrt{n}}$, we get the linear recurrence $S(n) = S(n/2) + 1$ with $S(1) = \frac{T(1)}{\sqrt{1}} = 1$.
Expanding this recurrence, we find $S(n) = S(n/2^m) + m = S(1) + \log_2 n = 1 + \log_2 n$.
Thus, $T(n) = \sqrt{n} S(n) = \sqrt{n}(\log_2 n + 1)$.

To solve $T(n) = 2T(\sqrt{n}) + 1$, let $n = 2^m$, which implies $m = \log_2 n$.
Substituting this into the recurrence gives $T(2^m) = 2T(2^{m/2}) + 1$.
Defining $S(m) = T(2^m)$, the equation becomes $S(m) = 2S(m/2) + 1$.
Using the Master Theorem with $a=2, b=2$, and $f(m) = 1$:
We compare $f(m)=1$ with $m^{\log_b a} = m^{\log_2 2} = m^1$.
Since $f(m) = O(m^{1-\epsilon})$ for $\epsilon = 1$, $S(m) = \Theta(m^1) = \Theta(m)$.
Substituting $m = \log_2 n$ back, we get $T(n) = \Theta(\log n)$.

The given recurrence is $T(n) = 2T(n/2) + \sqrt{n}$, which fits the Master Theorem form $T(n) = aT(n/b) + f(n)$ with $a=2$, $b=2$, and $f(n) = n^{0.5}$.
We compare $f(n) = n^{0.5}$ with $n^{\log_b a} = n^{\log_2 2} = n^1$.
Since $f(n) = O(n^{1-\epsilon})$ with $\epsilon = 0.5$, we apply Case 1 of the Master Theorem.
In Case 1, the complexity is dominated by the leaf nodes, resulting in $T(n) = \Theta(n^{\log_b a}) = \Theta(n^1) = \Theta(n)$.
Thus, the recurrence solves to $\Theta(n)$.

The recurrence $T(n) = 2T(n/2) + n$ follows the Master Theorem form $T(n) = aT(n/b) + f(n)$ with $a=2$, $b=2$, and $f(n)=n$.
Calculating $n^{\log_b a} = n^{\log_2 2} = n^1$, we observe that $f(n) = \Theta(n^{\log_b a})$.
Applying Case 2 of the Master Theorem, we obtain $T(n) = \Theta(n \log n)$.
Since $T(n) = \Theta(n \log n)$, $T(n) = O(n \log n)$ (Option D) and $T(n) = O(n^2)$ (Option A) are both true.
Because $n \log n$ grows asymptotically slower than $n^2$, the statement $T(n) = \Omega(n^2)$ is incorrect.

The correct matches are derived as follows:

1. Binary Search (P) reduces the search space by half each iteration, yielding $T(n) = T(n/2) + 1$ (IV).
2. Merge Sort (Q) divides the input into two equal halves and merges them, represented by $T(n) = 2T(n/2) + cn$ (III).
3. Quick Sort (R) involves partitioning the array around a pivot at index $k$, resulting in subarrays of size $k$ and $n-k$, given by $T(n) = T(k) + T(n-k) + cn$ (I).
4. Tower of Hanoi (S) requires moving $n-1$ disks twice plus one move for the largest disk, $T(n) = 2T(n-1) + 1$ (II).
   Matching these gives P-IV, Q-III, R-I, S-II.

The homogeneous solution for the recurrence $T(n) = 2T(n-1) + n$ is $T_h(n) = c \cdot 2^n$.
Assuming a particular solution $T_p(n) = An + B$, we substitute into the recurrence: $An + B = 2(A(n-1) + B) + n$.
Simplifying yields $An + B = (2A + 1)n + (2B - 2A)$, leading to $A = 2A + 1 \implies A = -1$ and $B = 2B - 2A \implies B = 2A = -2$.
The general solution is $T(n) = c \cdot 2^n - n - 2$.
Using the base case $T(1) = 1$, we find $1 = c \cdot 2^1 - 1 - 2$, yielding $2c = 4$, so $c = 2$.
Therefore, $T(n) = 2 \cdot 2^n - n - 2 = 2^{n+1} - n - 2$.

The recurrence relation $T(n+1) = T(n) + \lfloor \sqrt{n+1} \rfloor$ with $T(1)=1$ implies $T(n) = \sum_{k=1}^{n} \lfloor \sqrt{k} \rfloor$.
For $n = m^2$, we group terms by $j = \lfloor \sqrt{k} \rfloor$. Each $j$ for $j \in \{1, \dots, m-1\}$ corresponds to $2j+1$ values of $k$ where $\lfloor \sqrt{k} \rfloor = j$, plus the term $\lfloor \sqrt{m^2} \rfloor = m$ for $k=m^2$.
This gives $T(m^2) = \sum_{j=1}^{m-1} j(2j+1) + m = 2 \sum_{j=1}^{m-1} j^2 + \sum_{j=1}^{m-1} j + m$.
Using the formulas $\sum_{j=1}^{n} j^2 = \frac{n(n+1)(2n+1)}{6}$ and $\sum_{j=1}^{n} j = \frac{n(n+1)}{2}$ with $n=m-1$:
$T(m^2) = \frac{2(m-1)m(2m-1)}{6} + \frac{3(m-1)m}{6} + \frac{6m}{6} = \frac{m}{6} [2(2m^{2-}3m+1) + 3m - 3 + 6]$.
Simplifying the expression inside the brackets gives $4m^2 - 6m + 2 + 3m + 3 = 4m^2 - 3m + 5$.
Thus, $T(m^2) = \frac{m}{6} (4m^2 - 3m + 5)$.

Let $S(k) = T(2^{k})$, which transforms the recurrence into $S(k) = 3S(k-1) + 1$ with the base case $S(0) = T(1) = 1$.
The homogeneous solution is $S_{h}(k) = c \cdot 3^{k}$. For the particular solution $S_{p} = A$, solving $A = 3A + 1$ yields $A = -\frac{1}{2}$.
Combining these, the general solution is $S(k) = c \cdot 3^{k} - \frac{1}{2}$.
Applying the base case $S(0) = 1$, we get $1 = c - \frac{1}{2}$, which implies $c = \frac{3}{2}$.
Substituting $c$ back into the general solution gives $S(k) = \frac{3}{2} \cdot 3^{k} - \frac{1}{2} = \frac{3^{k+1}-1}{2}$.

The recurrence relation for the given procedure is $T(n) = T(\sqrt{n}) + O(1)$, where $T(n) = O(1)$ for $n \leq 2$.
To solve this, let $m = \log_2 n$, which implies $n = 2^m$ and $\sqrt{n} = n^{1/2} = 2^{m/2}$.
Substituting these into the recurrence gives $T(2^m) = T(2^{m/2}) + O(1)$.
Defining $S(m) = T(2^m)$, we obtain the recurrence $S(m) = S(m/2) + O(1)$.
Applying the Master Theorem (or iterative substitution), this simplifies to $S(m) = O(\log m)$.
Substituting back $m = \log_2 n$, the running time becomes $T(n) = O(\log(\log n))$.

We use the Master Theorem for the recurrence $T(n) = aT\left(\frac{n}{b}\right) + f(n)$ where $a=3$, $b=4$, and $f(n)=n$. Comparing $f(n)=n^1$ with $n^{\log_b a} = n^{\log_4 3} \approx n^{0.79}$, we observe that $f(n) = \Omega\left(n^{\log_4 3 + \epsilon}\right)$ for $\epsilon > 0$. The regularity condition $af\left(\frac{n}{b}\right) \leq cf(n)$ holds since $3\left(\frac{n}{4}\right) = \frac{3}{4}n \leq cn$ for $c=\frac{3}{4} < 1$. By Case 3 of the Master Theorem, $T(n) = \Theta(f(n)) = \Theta(n)$. Therefore, $T(n) = O(n)$.

Lucas numbers follow Fibonacci-like closed form using golden ratio.

Master theorem is standard for divide-and-conquer recurrences.

Here a = 4, b = 2, f(n) = n. Compute n^(log_b(a)) = n^(log_2(4)) = n^2. Compare f(n) = n with n^2: f(n) = O(n^(2 - 1)) = O(n^(log_b(a) - ε)) with ε = 1. This is Case 1 of the Master Theorem - the recursive work dominates. Therefore T(n) = Θ(n^log_b(a)) = Θ(n²).

Master Theorem applies to T(n) = aT(n/b) + f(n). T(n) = T(n-1) + n is a linear recurrence, not divide-and-conquer form.

T(n) = T(n/3) + T(2n/3) + n models the worst-case of QuickSort when the pivot always splits the array in ratio 1:2. The recursion tree has depth log_{3/2}(n) (the longest branch halves at rate 2/3). At each level, the total work is n (all subproblems together sum to n). Number of levels = O(log n). Total work = n × O(log n) = O(n log n). This can be formally verified by the Akra-Bazzi method.

To prove T(n) = O(n log n) by substitution, the inductive hypothesis is T(k) ≤ c × k × log k for all k < n. Substituting: T(n) = 2T(⌊n/2⌋) + n ≤ 2 × c × (n/2) × log(n/2) + n = c × n × (log n - 1) + n = c × n × log n - cn + n = c × n × log n - (c-1)n ≤ c × n × log n for c ≥ 1. The induction holds, confirming T(n) = O(n log n).

Here a = 4, b = 2, f(n) = n². Compute n^(log_b(a)) = n^(log_2(4)) = n². Compare f(n) = n² with n²: f(n) = Θ(n^log_b(a)) = Θ(n²). This is Case 2 of the Master Theorem. Therefore T(n) = Θ(n^log_b(a) × log n) = Θ(n² log n).

A: FALSE - the Master Theorem does NOT cover all cases. It fails when f(n) and n^(log_b(a)) differ by only a polylogarithmic factor (e.g., T(n) = 2T(n/2) + n log n), or when the recurrence has unequal subproblem sizes. B: TRUE - the substitution method requires first guessing the solution (often from intuition or the recursion tree) then proving it by induction. C: FALSE - the recursion tree typically gives an asymptotic estimate; it is used as a tool to guess the solution which is then confirmed by substitution. D: TRUE - f(n) = n log n vs n^(log_2(2)) = n falls between Case 2 and Case 3 with only a log factor difference, which the standard Master Theorem cannot handle.

Here a = 3, b = 4, f(n) = n log n. Compute n^(log_b(a)) = n^(log_4(3)) ≈ n^0.792. Compare f(n) = n log n with n^0.792: since n log n = Ω(n^(0.792 + ε)) for some ε > 0 (n dominates n^0.792), this is Case 3. Regularity: a × f(n/b) = 3 × (n/4) × log(n/4) ≤ (3/4) × n log n = c × f(n) with c = 3/4 < 1 ✓. Therefore T(n) = Θ(f(n)) = Θ(n log n).

Expanding: T(n) = T(n-2) + 1 = T(n-4) + 2 = ... After n/2 steps we reach T(2) or T(1). So T(n) = T(2) + n/2 - 1 = n/2 (approximately). Therefore T(n) = O(n). This recurrence models algorithms that reduce the problem by 2 at each step with O(1) work, such as checking if a string is a palindrome recursively.