Big O notation for recursive algorithm
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.