Timing for a recursive algorithm with constant combination time
Suppose I have a recursive algorithm that splits an input into 2 n-1 inputs and solves them recursively. It combines the results at a constant time, say c.
So, let's formulate the equation for this,
T (n) = 2T (n-1) + c
To find the complexity of this, I used the recursive tree method. Since the input is divisible by 2 at each step, the number of nodes will get a square at each step, whereas once only one item is eliminated, each level will lose only one item from the list.
Therefore, I believe that the complexity of this problem should be & Theta; (n 2 )
I am correct in this thought process. If not, what am I doing wrong?
Thank.
source to share
The number of nodes at each step does not get squared. Instead, it doubles up at every level. For example, the number of nodes in
- problem size n: 1
- problem size n - 1: 2
- problem size n - 2: 4
- problem size n - 3: 8
- problem size n - 4: 16
- ...
- size of problem n - i: 2 i
As a result, the total number of nodes in the recursion tree will be 1 + 2 + 4 + 8 + ... + 2 n = 2 n + 1 - 1. Accordingly, the work done will be c2 n + 1 - c, which is? (2 n ). This is exponential time, not quadratic time.
Hope this helps!
source to share
Complexity is actually exponentially Omega(2^n)
.
Prove this using mathematical induction . For simplicity, supposec=1
Claim: T(n) >= 2^n
Base: T(0) = 1 (Let take it as assumption)
Assume the claim is true for each k<n and using it let prove:
T(n) = 2*T(n-1) + 1 >= 2*2^(n-1) + 1 = 2^n + 1 > 2^n
Now, to complete it, let it show that this is also O(2^n)
, and we will end this Theta(2^n)
::
Claim: T(n) <= 2*2^n - 1
Base: T(0) = 1 = 2 -1
Assume the claim is true for each k<n and using it let prove:
T(n) = 2*T(n-1) + 1 <= 2 * (2*2^(n-1) -1 ) + 1 = 2*2^n -2 + 1 = 2*2^n -1
As you can see, we actually end up with exactly 2*2^n-1
(The <= can be easily replaced with = in the above proof), which is what @templatetypedef showed
source to share