Problem
unsigned int f(unsigned int n){ if(n==0 || n==1) return 0; if(n%2==0) return 1+f(n/2); return 1+f(5*n+1); }$1.$ What can we conclude about $f$ as a function $\mathbb{N}\to \mathbb{N}$? $~~~2.$ What is the time complexity of the above function?
$1)$ I have tried to find different output for different values of $n\in \mathbb{N}$. It is not clear how to classify the outputs for special types of outputs. For example, $f(5)$ never terminates. Here is the diagram, arrow represents calls, $c$ stores the value to be return -
$$f(5)\to \underbrace{f(26)}_{c=1}\to \underbrace{f(13)}_{c=2}\to \underbrace{f(66)}_{c=3}\to \underbrace{f(33)}_{c=4}\to \cdots \to \underbrace{f(13)}_{c=12}\to f(66)\to \cdots$$
Here it forms a loop, and the function will never returns any value. I thought probably for primes the function will never terminate, but, $f(19)=11$. The special thing I have observed that, for any number in the chain of $5$ the program will never return a value. I think breaking $n$ as $2^k\cdot p$, with $(p,2)=1$ can help. If we hit a power of $2$ in the chain, after that we will need $\log_2{k}$ many steps more, where $k$ is the power of $2~$(In case of $19$ we hit $16$ after some steps).
Can we conclude about outputs about special types of inputs?
$2)$ Suppose $T(n)$ is the complexity. Then, $$T(n)=\begin{cases} T(n/2)+c_1 & \text{ when n is even} \\ T(5n)+c_2 & \text{ when n is odd} \end{cases}$$
But here after first step how we can use recurrence relation? $n/2$ can be even as well as odd also. In each step we will have two cases. I haven't handled this type of recurrence before and out of idea.
How I can find $T(n)$ ?