Time Complexity of $T(n) = 3T(n-1) + n$
The time complexity of the recurrence relation $T(n) = 3T(n-1) + n$ is $\Theta(3^n)$.
1. Expansion The recurrence is expanded repeatedly: * $T(n) = 3T(n-1) + n$
$T(n) = 3[3T(n-2) + (n-1)] + n = 3^2T(n-2) + 3(n-1) + n$
$T(n) = 3^2[3T(n-3) + (n-2)] + 3(n-1) + n = 3^3T(n-3) + 3^2(n-2) + 3(n-1) + n$
2. General Pattern After $k$ steps, the general form is: $$T(n) = 3^k T(n-k) + \sum_{i=0}^{k-1} 3^i (n-i)$$ 3. Solving for the Base Case Assuming a base case $T(0) = c$, we set $k=n$: $$T(n) = 3^n T(0) + \sum_{i=0}^{n-1} 3^i (n-i)$$ 4. Closed-Form Solution Solving the summation gives the exact closed-form solution: $$T(n) = \left(c + \frac{3}{4}\right) \cdot 3^n - \frac{n}{2} - \frac{3}{4}$$ The **dominant term** is proportional to $3^n$, so the final complexity is $\Theta(3^n)$.
