# Big O notation for recursive algorithm [duplicate]

In order to find Big O for a recursive algorithm, it is needed to know the stopping criteria of that algorithm. For the recursive algorithm to find Factorial of a number it is very easy to find the stopping criteria.

int fact(int n)
{
if((n==1)||(n==0)) return 1;
else retrun n*fact(n-1);
}


And we can make a mathematical definition of this problem as follow:

$fact(n)= \begin{cases} 1,& \text{if } n = 1 \vee n=0\\ n*fact(n-1), &{otherwise} \end{cases} \tag{1}$

Now my question is how is the correct mathematical definition for this algorithm:

void func(int n)
{
if(n>0)
{
func(n-1);
}
else
{
print(n)
}
}


Also, for the same algorithm if I change it as follow what is the stopping criteria and the mathematical definition of it?

int n = 5;
int rnd; // Random number between 0 and n
void func(n)
{
if(n>rnd)
{
func(n-1);
}
else
{
print(n)
}
}


Now the stopping criteria is random? So how can I define this in order to find Big O?

For the first algorithm, you get the recurrence $$T(0) = \Theta(1), \quad T(n) = T(n-1) + \Theta(1) \text{ for n > 0},$$ whose solution is $T(n) = \Theta(n)$.
For the second algorithm, the recurrence depends on $rnd$: $$T(rnd) = \Theta(1), \quad T(n) = T(n-1) + \Theta(1) \text{ for n > rnd}.$$ The solution to this recurrence is $T(n) = \Theta(n-rnd+1)$. The expected value of $T(n)$ (if $rnd$ is chosen uniformly at random) is $\Theta(n)$, since $\mathbb{E}[rnd] = \frac{n}{2}$.
Each recursive function should have some initial values to stop the computation. For the last two recursive functions, the program will not be stopped and trapped in an infinite loop or it has no meaning (for case 2, what is the value of $f(1)$?). Also, for the last case, if we have a random initial value, we can compute the complexity in average: $$\frac{1}{n}(n + (n-1) +\cdots+1)=O(n)$$ As Probability of each random value between $1$ to $n$ is $\frac{1}{n}$, the average complexity is $O(n)$, as shown in the above.
• @J.Doe Ok. So it has no meaning. What is the value of $f(1)$ in the second case? you should have else part in your functions. – OmG Feb 21 '18 at 12:52
• @J.Doe we have nothing like that in the common languages. Anyhow, in an unrealistic case, time complexity of the second case is $\Theta(n)$ and the latest case is $O(n)$ in average. – OmG Feb 21 '18 at 12:56