I need to find the complexity of an algorithm that involves the recurrence:
T(n) = T(n-1) + ... + T(1) + 1
T(n)
is the time it takes to solve a problem of size n
.
The master method doesn't apply here and I can't make a guess to use the substitution method (I don't want to use the substitution method anyway). I'm left with recursion tree method.
Since the number of children of each node isn't a constant, I'm finding it hard to keep track of how much each node contributes. What is the underlying pattern?
I understand that I have to find the number of nodes in a tree in which each node (k
) has for its children all nodes numbered from 1 to k-1
.
Is it also possible to find the exact time T(n)
given that formula?
Since T(n-1) = T(n-2) + ... + T(1) + 1
T(n) = T(n-1) + T(n-2) + ... + T(1) + 1
= T(n-1) + T(n-1)
= 2*T(n-1)
and T(1) = 1
=> T(n) = 2^(n-1)