What would be the time complexity of below recursive function-CodePudding

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;
}

CodePudding user response：

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

CodePudding user response：

I am going to tackle this problem from a mathematical point of view.

first of all, 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.

CodePudding user response：

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!)

CodePudding user response：

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.

CodePudding user response：

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

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)!)