[Solved] Time complexity of recursive algorithm (pseudo code)

by


First, let’s look at two simple nested loops first:

for i (1..N) {
   for j (1..N) {
      f();
   }
}

for i (1..N) {
   for j (i..N) {
      g();
   }
}

f() is called N*N = N2 = O(N2) times.

g() is called N+(N-1)+...+5+4+3+2+1 = N(N+1)/2 = N2/2 + N/2 = O(N2) times.

As you can see, it doesn’t matter where the inner loop starts; the complexity is going to be the same.

Secondly, let’s see what happens if you add a level of nesting.

for i (1..N) {
   for j (1..N) {
      for k (1..N) {
          h();
      }
   }
}

We already know the two outer loops are O(N2), and we are doing that N times, so we get O(N3). We can see that the exponent is the amount of nesting.

If we start unrolling recursive, we get

for i2 = i+c to a
    recursive(i2, b-1)

which is

for i2 = i+c to a
   for i3 = i2+c to a
       recursive(i3, b-2)

which is

for i2 = i+c to a
   for i3 = i2+c to a
       for i4 = i3+c to a
           recursive(i4, b-3)

etc

As you can see, you have b nested loops that iterate over a subset of a-c elements. Applying what we learned above, recursive takes O((a-c)b) time.

The whole code (i.e. the call to recursive plus the outer loop) adds another layer, so it takes O((a-c)b * a) time.

0

solved Time complexity of recursive algorithm (pseudo code)