Time complexity of recursive function with a loop-CodePudding

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?

CodePudding user response：

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.

CodePudding user response：

By drawing recursion tree you already halfway to the solution already (but you should have draw with a generic N term instead of constants).

T(N) = C*N   2*C*(N-1)   4*C*(N-2)   8*C*(N-3) ...   
T(N) = 2^0 * C*N   2^1 * C*(N-1)   2^2 * C*(N-2)   2^3 * C*(N-3) ...

Rearrange terms a little:

T(N) = (2^0*C*N   2^1*C*N   2^2*C*N ...) - (0   2^1*C   2^2 *2*C ...)

Geometric series on left is: 2^0 2^1 2^2 ... is equals to 2^(N 1) - 1 Geometric series on the right is: 2^1 2^2 .... is equals to 2^(N 1) - 2 , due to missing first term

T(N) = (2^(N 1) - 1)*C*N  -  (2^N 1) - 2)*C

If you ignore the constants, on the left side you have: 2^N * N and on the right side you have: 2^N

Larger term is 2^N * N