Complexity of recursive algorithm.

Question

An algorithm solves problems of size $n$ by recursively solving two subproblems of size $n - 1$ and then combining the solutions in constant time.

What is the algorithms running time?

Assume $ T(1)\in O(1)$

So far I have:

$$T(n) \le 2T(n - 1) + c$$

After a recursion:

$$T(n) \le 2(2T(n - 2) + c) + c$$

$$= 4T(n - 2) + 3c$$

After every recursion:

$$T(n) \le 2^{n - 1} + 2(n - 1)c + c$$

$$= 2^{n - 1} + 2nc - c$$

As the algorithm can recurse a total of $n - 1$ times.

Hence: $$T(n) \in O(2^{n - 1})$$

$$ \in O(2^{n})$$

This question is from Algorithms; Dasgupta, Papadimitriou, Vazirani; 1st Edition. Question 2.4

Thank you.

Answer 1

You can solve the recurrence $T(n)=2T(n-1)+c$ directly. The general solution is of the form of the sum of a solution of the homogeneous equation $T(n)=2T(n-1)$ and a particular solution of the full equation.

The general solution of the homogeneous equation is: $T(n)=A\times 2^n$. Also as the right hand side has a constant term added to the homogeneous form we look for a particular solution which is constant. Trying this we find that T(n)=-c is a particular solution.

Hence the general solution is of the form: $T(n)=A \times 2^n-c$, where the value of $A$ would be determined by the initial condition. Hence $T(n) \in O(2^n)$.

Answer 2

$T(n)2^{-n} = T(n-1)2^{-(n-1)} + c2^{-n}$ and hence $T(n)2^{-n} = T(0)2^{-0} + \sum_{k=1}^n c2^{-k}$.