If we have a function:-
int x=0;
int fun(int n)
{
if(n==0)
return 1;
for(int i=0; i<n;i++)
x += fun(i);
}
According to me, time complexity can be calculated as:-
T(n) = T(n-1) + T(n-2) +...+ T(0).
T(n) = nT(n-1).
T(n) = O(n!).
Am I correct?
1. T(n) = T(n-1) + T(n-2) + T(n-3) + .... + T(0)
// Replace n with n-1
2. T(n-1) = T(n-2) + T(n-3) + .... + T(0)
Replace T(n-2) + T(n-3) + .... + T(0) with T(n-1) in 1st Equation
T(n) = T(n-1) + T(n-1)
= 2 * T(n-1)
= 2 * 2 * T(n-2) // Using T(n-1) = 2 * T(n-2)
= 2^n * T(n-n)
= 2^n * T(0) // Consider T(0) = 1
= 2^n
If you're measuring the number of function calls (or additions -- it turns out the same), the correct recurrence relations are:
T(0) = 0
T(n) = T(0) + T(1) + T(2) + ... + T(n-1) + n
You can compute the first few values:
T(0) = 0
T(1) = 1
T(2) = 3
T(3) = 7
T(4) = 15
You can guess from this that T(n) = 2^n - 1, and that's easy to check by a proof by induction.
In some sense you are right that T(n) = O(n!) since n! > 2^n for n>3, but T(n) = O(2^n) is a tighter bound.
