time complexity of recursion function

Question

I don't know where to start to calculate the time complexity of this function. What is O(time complexity) of this function? I learned that the answer is 3^n.

int f3(int n) {
    if (n < 100)
        return 1;
    return n* f3(n-1) * f3(n-2) * f3(n-3)
}

For starters, it has a different time complexity depending on whether `n >= 100` or not. Manually run through the code for `n=103` and extrapolate. Also, this will overflow `int` pretty quickly. — Jim Garrison, Dec 15 '17 at 06:13
This has been answed before just need to look at it [Here](https://stackoverflow.com/questions/16917958/how-does-if-affect-complexity) — Roland Mate, Dec 15 '17 at 06:14
I think that we should calculate it from n to 103. After 103 it is not important to look at the others but I couldn't figure it out. — Süleyman Acar, Dec 15 '17 at 06:17
Start by writing down the recurrence relation for the complexity. — Paul Hankin, Dec 15 '17 at 06:21
@AditiRawat because adding TurboC++ would have been a gauche overreach. — user4581301, Dec 15 '17 at 06:46
Recommended read: https://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation — Aditi Rawat, Dec 15 '17 at 07:13
If you develop the call tree you will easily see that for any great $n$ the tree has degree 3 and that every path from the root to a leave has length of order $n$. — Jean-Baptiste Yunès, Dec 15 '17 at 13:14
I am amazed that WHY SO members down vote this question !!! It is so similar to [this question:today](https://stackoverflow.com/questions/47836794/time-complexity-of-the-code-containing-condition). — Gholamali Irani, Dec 15 '17 at 18:36

score 4 · Accepted Answer · answered Dec 15 '17 at 20:31

We have:
1 : if statement
3 : * operator
3 : function statement
Totally: 7

So we have:

T(n)=t(n-1) + t(n-2) + t(n-3) + 7
T(99)=1
T(98)=1
...
T(1)=1

Then to reduce T(n), we have T(n-3)<T(n-2)<T(n-1) therefore:

T(n) <= T(n-1)+T(n-1)+T(n-1) + 7
T(n) <= 3T(n-1) + 7

So we can solve T(n) = 3T(n-1) + 7 (in big numbers T(n-1) is almost equal T(n-2) and ... )

Then we can calculate T(n) by following approach:

T(n) = 3.T(n-1) + 7
     =3.(3.T(n-2)+7) + 7     = 3^2.T(n-2) + 7.(3^1 + 3^0)
     =3^2.(3.T(n-3)+7) + ... = 3^3.T(n-3) + 7.(3^2 + 3^1 + 3^0)
                             = 3^4.T(n-4) + 7.(3^4 + 3^2 + 3^1 + 3^0)
     ...
     =3^(n-99).T(n-(n-99)) + 7.(3^(n-98) + 3^(n-97) + ...+ 3^1 + 3^0)
     =3^(n-99) + 7.(3^(n-98) + 3^(n-97) + ...+ 3^1 + 3^0)

So consider that 1 + 3 + 3^2 ...+3^(n-1) = 3^n - 1/2

Therefore we reached:

T(n) = 3^(n-99) + 7.(3^(n-99) + 1/2) = 8.3^(n-99) - 7/2
     = 8/(3^99) . 3^n -7/2

Finally: Big O is O(3^n)

If you just have T(1)=1, the answer is the same.

time complexity of recursion function

1 Answers1