I have the following Python code.

def collatz(n): if n <= 1: return True elif (n%2==0): return collatz(n/2) else: return collatz(3*n+1) 

What is the running-time of this algorithm?

Try:

If $T(n)$ denotes the running time of the function collatz(n). Then I think I have \begin{cases} T(n)=1 \text{ for } n\le 1\\ T(n)=T(n/2) \text{ for } n\text{ even}\\ T(n)=T(3n+1) \text{ for } n\text{ odd}\\ \end{cases}

I think $T(n)$ will be $\lg n$ if $n$ is even but how to calculate the recurrence in general?