Time complexity of recursive function with a loop

Question

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?

Are you sure that the provided code is C++ and not JavaScript? — justANewb stands with Ukraine
– justANewb stands with Ukraine, Commented Dec 27, 2021 at 7:46
Each function call takes linear time, so probably 2^n times n. — kiner_shah
– kiner_shah, Commented Dec 27, 2021 at 7:46
You have the right equation for the time complexity. You can just plug it into wolfram alpha to get the answer: wolframalpha.com/input/?i=sum%282%5Ei%28n-i%29%2C+i%3D0..n%29 . By hand, sum(i*2^i) can be calculated as x * d/dx(sum(x^i) evaluated at x=2. You need to be careful about the limits of the sums which I've omitted in this comment. — Paul Hankin
– Paul Hankin, Commented Dec 27, 2021 at 9:28
The old-school way for recurrence relations is to guess the answer and then prove it. You can use wolfram alpha to replace the part when you have to guess (which in general requires experience in solving the specific type of equation you have, or work to plot numbers and get insight about the answer that way). You still have a valid proof once you've finished! — Paul Hankin
– Paul Hankin, Commented Dec 27, 2021 at 9:32

score 1 · Accepted Answer · 2021-12-27 08:45:16Z

1

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.

edited Dec 27, 2021 at 8:45

answered Dec 27, 2021 at 7:58

user1196549

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

7 Comments

unlut Over a year ago

Are you sure its just 2^N? If equation was T(n) = C2 + 2 T(n-1) it would be 2^N already, but here we have an additional N term.

user1196549 Over a year ago

@unlut: this was a typo. There is no N in my development.

user1196549 Over a year ago

@unlut: if you mean that the solution should have a term n.2^n, I say no. (wolframalpha.com/input/…)

unlut Over a year ago

I did not know wolframalpha could be used for these, thanks for that. I will find out what was my mistake in my solution.

user1196549 Over a year ago

@unlut: there is no need for Alpha, in fact. This finite difference equation is not difficult.

|

Collectives™ on Stack Overflow

Time complexity of recursive function with a loop

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related