CODEWITHSUNDEEP
algorithmperformancetime-complexity
LoveScience
LoveScience

Reputation: 29

I don't understand this algorithm's Time Complexity

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?

Upvotes: 3

Views: 131

Answers (2)

displayName
displayName

Reputation: 14399

@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. 2The total number of nodes in a complete binary tree is given by simple formula (2n - 1 - 1).

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

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.

Upvotes: 3

blazs
blazs

Reputation: 4845

We have a recurrence relation T(n) = c+2*T(n-1) for some constant c>0. We also need a boundary condition, otherwise the recurrence is not well-defined. Let us assume that T(1) = c.

Computing the first few values, T(2)=c+2c, T(3)=c+2c+4c, we are tempted to conjecture that T(n) = c * (2^n-1).

Let us prove this by induction on n. For the base case,when n=0, we have T(1)=c*(2^1-1)=c*1=c which is okay.

Now assume that T(k) = c*(2^k-1) for all k<=n. For the inductive step, we compute T(n+1) = c+2*T(n) = c + 2*(c * (2^n-1)) = c + c * 2^{n+1} - 2*c = c * 2^{n+1}-c = c*(2^{n+1}-1). This proves the claim.

Asymptotically we have T(n) = O(2^n).

Upvotes: 3

Related Questions