CODEWITHSUNDEEP
c++recursionruntimebig-o
alepfu
alepfu

Reputation: 69

Theta runtime of recursion

How do I calculate the Theta runtime of this given code:

void f(int n)
{
    for (int i=3; i<n; ++i)
        for (int j=0; j<i; ++j)
            f(n-1);
}

So far i got this, but I don't know if it's right or how to bring it in Theta notation.

f(n) = n^2 * f(n-1)
f(n) = n^2 * (n-1)^2 * f(n-2)
f(n) = n^2 * (n-1)^2 * (n-2)^2 * f(n-3) 
...

Upvotes: 2

Views: 343

Answers (2)

leftaroundabout
leftaroundabout

Reputation: 120711

If we replace that 3 with a zero (which obviously doesn't change anything about the Θ) we can very easily derive the exact amount of function calls:

Θf ( 1 ) = 1
Θf ( n ) = n2 ⋅ Θf ( n-1 )         ∀ n > 0

So, using commutativeness of the product,

                  n                 n          n
Θf ( n ) =   ∏   j 2   =   ∏ j   ⋅  ∏ j  =  n! ⋅ n!
               i =1             i =1     i =1
= (n!)2

As Jason said.

Upvotes: 1

Jason
Jason

Reputation: 32510

Since each nested for-loop is O(N^2) complexity, and each time you call a function inside another function, the complexity is multiplied, you end up with O((N!)^2), where N is also the number of times you recurse. This is of course because N! = N*(N-1)*(N-2)*...*(N-N+1), and all the values used to create the factorial are squared.

Upvotes: 2

Related Questions