What would be the time complexity of below recursive function

Question

What would the time complexity be for the below recursive function?

I am using the the below T(n) but not sure if I created the correct equation for this function

T(n)=T(n-1)+n -> o(n^2)

public static int test2(int n){
    if(n<=0){
        return 0;
    }
    for(int i =0; i<=n; i++){
        for(int j =0; j<=n; j++){
            System.out.println(" in here " + i + j);
        }
        test2(n-1);
    }
    return 1;
}

o(n^3). Each recusive step is o(n^2) beacuse of the nested loop. But the recursion itself is nothing more than a glorified loop. I think this explanation helps you understand https://stackoverflow.com/a/61297030/3071712 — Marko Taht, Nov 21 '22 at 20:19
@MarkoTaht: Wouldn't it be O(n^3) if `test2` was called from *outside* the loops? — Scott Hunter, Nov 21 '22 at 20:26

score 1 · Answer 1 · answered Nov 21 '22 at 20:33

1

I think the function is: T(n)=n(T(n-1))+n^2

answered Nov 21 '22 at 20:33

הילה לויטן

21
1

Alexander Ivanchenko · Answer 2 · 2022-11-21T21:15:55.793

0

O(n^2) is the Time complexity of a single non-terminating recursive call, but not the overall Time complexity.

Each call test(n), if it doesn't hit the Base case of the recursion, creates n + 1 branches of recursive calls.

For instance, if n = 2. The tree of recursive calls would be:

               t(2)
           /    |   \
          /     |    \
      t(1)     t(1)   t(1)
      /  \     /  \    /  \
  t(0) t(0) t(0) t(0) t(0) t(0)

So the call test(2) results in 9 recursive calls. If we call test(3) it would spawn 40 recursive calls.

Basically we have:

(n) * (n + 1 - 1) * (n + 1 - 2) * (n + 1 - 3) * ... until `n` doesn't turn to 1

Which resembles a factorial, if we neglect +1 and it would be roughly n! recursive calls. Each of which would have a time complexity O(n^2)

So the overall time complexity can be expressed as:

O(n^2 * n!)

edited Nov 21 '22 at 21:15

answered Nov 21 '22 at 20:47

Alexander Ivanchenko

25,667
5
22
46

There are indeed O(n!) recursive calls, but each matches the execution of the inner loop only. So the total complexity is O(n.n!). – Nov 21 '22 at 22:07
@YvesDaoust Sorry, can you explain please. Each call that doesn't hit the Base case performs `O(n)` iterations of the outer loop. Every iteration step spawns a new recursive branch and perform `O(n)` `println()` calls. Which should result in `O(n * n)` `println()` calls, isn't it? Am I missing something? – Alexander Ivanchenko Nov 21 '22 at 22:25
This is for n recursive calls of f2, not one. The number of prints is very close to C.(n+1)! – Nov 22 '22 at 07:52

RunTimeError31415 · Answer 3 · 2023-02-19T10:37:30.687

Your equation for T(n) is not correct it should be:

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

The reason being that you have n iterations and for every iteration (this is where the product comes), you do a recursion along with n iterations. So basically you will have:

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

where T(0) = 1 basically given your definition. So now with a bit of reordering and multiplication you will have:

T (n) = n^2 + n*((n-1)^2) + n*(n-1)*((n-2)^2) + ... + n*(n-1)*(n-2)*(n-3)*...*(n-(n-3))*(2^2) + (2 * n!)

the reason for that last 2 * n! is that T(1) = 2 and through the multiplications it gets a coefficient of n!. (Do to the process just basically start from T(n-1) and by multiplying the equation with n and adding it to the equation of T(n) you get rid of T(n-1). But you now have T(n-2) in the equation of T(n) so repeat the process) So I think (but am not sure) that the time complexity will be n! and not n^2. I hope this is helpful.

score 0 · Answer 4 · 2022-11-21T22:15:02.090

Replacing the operations by the time they take, you establish the following recurrence:

T(0) = C0
T(n) =
    Σ{i=0..n}
        Σ{j=0..n}
            C1
        +
        T(n-1)
    + C2

This can be rewritten

T(n) = (n+1).((n+1).C1 + T(n-1)) + C2 = (n+1).T(n-1) + (n+1)².C1 + C2

The exact solution of this recurrence is a little technical. By solving the homogeneous equation, we have the solution C.(n+1)! and by variation of the coefficient we set

T(n) = (n+1)!.U(n)

Then

(n+1)!.U(n) = (n+1).n!.U(n-1) + C1.(n+1)² + C2

or

U(n) = U(n-1) + C1/(n-2)! + 2C1/(n-1)! + C2/(n+1)!

We recognize truncated series for e, which very quickly converges to a constant and

T(n) ~ C(n+1)! = O((n+1)!)

score 0 · Answer 5 · answered Nov 21 '22 at 21:54

This is a rather complex function. Lets move from bottom up and maybe we can see something.

T(0) = 1
T(1) = 2 * (2 + T(0)) = 2 * (2 + 1) = 2 * 3 = 6
T(2) = 3 * (3 + T(1)) = 3 * (3 + 6) = 2 * 9 = 27
T(3) = 4 * (4 + T(2)) = 4 * (4 + 27) = 4 * 31 = 124

If we expand it differently

T(1) = 2 * (2 + T(0))
T(2) = 3 * (3 + 2 * (2 + T(0)))
T(3) = 4 * (4 + T(2)) = 4 * (4 + 3 * (3 + 2 * (2 + T(0))))
...
T(n) = (n+1) * (n+1 + T(n)) = (n+1) * (n+1 + n * (n + T(n -1))) =
(n+1) * (n+1 + n * (n + (n-1) * ((n-1) + T(n-2))))

Now if we open parenthises of T(n)

T(n) = (n+1)^2 + (n+1)n*(n + T(n-1)) = (n+1)^2 + (n+1)n^2 + (n+1)n(n-1)*((n-1) + T(n-1)) = ... 
= (n+1)^2 + (n+1)n^2 + ... + (n+1)n(n-1)...2^2 + (n+1)! = Sum[iProduct[j,{j,i,n}],{i,2,n}] + (n+1)!

(I used wolfram alpha for the sum thing, i hope tis correct)

What can we see from the final sum is that the largest member of the sum is (n+1)! Everything else will be smaller, so we can disregard those. Also the +1 is pointless so we can also drop that. End result is that your recursive function is o(n!).

If anyone asks why n+1, it because the loop condition is i<=n not i < n. Also i havent done this type of analysis for quite some years now, i hope i didnt make any major mistakes.

What would be the time complexity of below recursive function

5 Answers5