I don't understand this algorithm's Time Complexity

Question

In an exercise I had it is found that an algorithm with complexity: T(n)=c+2T(n−1)

can be given by T(n)=c⋅2n which is of complexity order O(2^n).

Does someone understand how?

Answer 1

_{@blazs's answer seems correct. If that helps you understand, that's great. Here is an answer for visual learners like myself...}

---

The recurrence you have provided is: T(n) = c + 2T(n−1)

• So, on each node of the recurrence tree, you do a constant work c. Given that the work you are doing on each node is constant, if you can find the upper limit of total number of nodes in the tree, you have found the complexity!

• According to your recursion, you effectively break a problem of size n to two problems of size n - 1. So, at every level the tree actually grows to a max of twice its size on the previous level. It is a complete binary tree with depth of n. ²The total number of nodes in a complete binary tree is given by simple formula (2^{n - 1} - 1).

Multiplying it by 2, gives us number of nodes is proportional to 2ⁿ - 2. Hence, the complexity represented by the recurrence is = O(2ⁿ).

---

Some useful points:

^{1. In the method of recursion trees, the complexity of the algorithm is equal to the sum of work done at each level of the tree.}

^{2. The simple formula about the number of nodes in a complete binary tree of height n.}

^{3. A beautiful explanation of summation of powers of two in binary is given on Math StackExchange.}

^{4. You see how you are solving a problem of size n by solving two problems of size n - 1. And because you solve each subproblem multiple times, you end up with exponential complexity. What would happen if you would solve the n - 1 sized problem only once and then cache it for future lookup? You would vastly reduce the complexity of this problem from O(2n) to O(n)!! This caching is called Memoization and this approach to solving the subproblems only once has the popular and fearsome name Dynamic Programming.}