0
$\begingroup$

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.

$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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)$.

$\endgroup$
0
0
$\begingroup$

$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}$.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.