Time complexity of recursive function with a loop

user_11220479 0
Viewed 321

What would be the time complexity of the below function?

int f = (int n) => {
  if (n === 1) {
    return 1;
  }

  for (let i = 0; i < n; i++) {
    console.log(i);
  }

  return f(n-1) + f(n-1)
}

This is what the recursion tree looks like where i denotes the depth:

                   f(4)                         // i = 0
                  /    \
                /        \
              /            \
            /                \
          /                    \
        f(3)                  f(3)              // i = 1
       /   \                  /   \
     /       \              /       \
   f(2)      f(2)         f(2)      f(2)        // i = 2
  /   \     /   \        /   \     /   \
f(1) f(1) f(1) f(1)    f(1) f(1) f(1) f(1)      // i = 3

Had there been no loop inside the function, the time complexity would have been O(2^n). But now there's a loop so:

At each depth, the number of function calls made is 2 ^ i and in each function call n - i iterations are done in the loop, hence at each level (2 ^ i) * (n - i) operations are being done. So, time complexity could be calculated as:

T(n) = [(2 ^ 0) * (n - 0)] + [(2 ^ 1) * (n - 1)] + [(2 ^ 2) * (n - 2)] + ... + [(2 ^ (n - 1)) * (n - (n - 1))]

So am I right on this and what could possibly be the final time complexity?

recursion time-complexity algorithm loops
1 Answers

You are right, the number of log calls is driven by the recurrence

T(n) = C1 n + C2 + 2 T(n-1)

with T(1)=C3.

We can guess that the solution has the form

T(n) = A 2^n + B.n + C

and by identification,

T(n) = A 2^n - C1 n - C2 + C1.

Finally,

T(1) = 2 A - C2 = C3

gives A.

user_11965490
Related