Complexity of a recursive algorithm

Question

I have a recursive algorithm like :

int alg(int n) {
  if (n == 0)
    return 2;
  for (int i = 0; i<= n-1; ++i)
    alg(i);
}

Obviously the n == 0 case is Θ(1). However I am having trouble understanding how it really works. I mean it must be something like :

T(n) = T(0) + T(1) + ... + T(n-1).

And then we have to give T(1), T(2), .., T(n-1) = xT(0). I can understand the way it goes for n=0 and n=1, but for bigger n it goes wrong.

looks O(aragh!) to me. I wouldn't know how to analyse it properly, but it looks to be related to O(n!), which is about as bad as it gets. — Dave
– Dave, Commented May 12, 2013 at 2:06

vidit · Accepted Answer · 2013-05-12 02:14:00Z

15

You can observe that:

T(n)     = T(0) + T(1) + ... + T(n-2) + T(n-1)
T(n - 1) = T(0) + T(1) + ... + T(n-2)

Therefore

T(n)     = 2 * T(n-1)

At this point, we can conclude that the complexity is O(2ⁿ). Actually, it is Θ(2ⁿ).

vidit

6,5013 gold badges36 silver badges50 bronze badges

answered May 12, 2013 at 2:08

nhahtdh

56.9k15 gold badges131 silver badges164 bronze badges

Sign up to request clarification or add additional context in comments.

1 Answer 1