How long does the Collatz recursion run?

Problem Detail: 

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?

Asked By : 9bi7

Answered By : Evil

This is Collatz conjecture - still open problem.
Conjecture is about proof that this sequence stops for any input, since this is unresolved, we do not know how to solve this runtime recurrence relation, moreover it may not halt at all - so until proven, the running time is unknown and may be $\infty$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54266