1. **Problem Statement:** Find the time complexity of the recurrence relation $$T(n) = 2T(n-1) + 1$$. 2. **Formula and Approach:** This is a linear non-homogeneous recurrence relation. To solve it, we use the method of iteration or characteristic equations. 3. **Iteration Method:** - Start expanding the recurrence: $$T(n) = 2T(n-1) + 1$$ $$T(n-1) = 2T(n-2) + 1$$ Substitute back: $$T(n) = 2(2T(n-2) + 1) + 1 = 2^2 T(n-2) + 2 + 1$$ 4. Continuing this expansion for k steps: $$T(n) = 2^k T(n-k) + (2^{k-1} + 2^{k-2} + \cdots + 2 + 1)$$ 5. When $k = n-1$, assuming base case $T(0) = c$ (constant): $$T(n) = 2^{n-1} T(0) + (2^{n-2} + 2^{n-3} + \cdots + 2 + 1)$$ 6. The sum of the geometric series is: $$\sum_{i=0}^{n-2} 2^i = 2^{n-1} - 1$$ 7. Substitute back: $$T(n) = 2^{n-1} c + (2^{n-1} - 1) = 2^{n-1} (c + 1) - 1$$ 8. **Conclusion:** The dominant term is $2^{n-1}$, so the time complexity is exponential: $$T(n) = O(2^n)$$. This means the time grows exponentially with $n$, doubling at each step.