Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
4  
That should be $T(n) = T(\frac n2) + 1$ and so on. The +1 is important, otherwise you have $T(n) = 1$, for all $n$ for which the sequence terminates. – immibis Mar 11 at 1:45
2  
54 is even, T(54) = 112 != lg(54) – Taemyr Mar 11 at 11:08
    
Is it assumed that user will only input integer? – Dean MacGregor Mar 11 at 15:54
    
@DeanMacGregor Yes. In fact, a positive integer is assumed. – duskwuff Mar 12 at 0:28
    
more bkg detail would be helpful. where did you get the code, how were you introduced to it? this is a semifamous open problem in number theory unsolved for ~¾ century on which an entire book by Lagarias has been written. from CS pov proving it is in any time or space complexity class is equivalent to a proof. many more refs here. also a great topic for Computer Science Chat for anyone interested. there is also a collatz tag on MathOverflow etc. latest research shows problem has intrinsic fractal qualities making it hard. – vzn Mar 12 at 17:55
up vote 28 down vote accepted

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$.

share|cite|improve this answer
    
Thanks. But my recursion is true right? If so, then we still cannot find the solution for that recursion? – 9bi7 Mar 10 at 18:44
    
What do you mean by "reccursion is true"? You cannot find running time, but for a lot of numbers this will make some number of jumps and get to 1. $T(n)$ does not denote runtime but the function itself. – Evil Mar 10 at 18:55
    
By correct I meant for example like in merge sort we can get $T(n)=2T(n/2)+O(n)$. Since the code is recursive, we can write the recurrence for it, right? – 9bi7 Mar 10 at 19:26
6  
"since this is unresolved, there is no upper bound" -- we have to be careful with the language here. We do not know the solution of this recurrence, end of story. – Raphael Mar 10 at 21:05
7  
Yes. But "we don't know" is not the same as "there is no upper bound". Basically, I am splitting hairs over mathematical "there is" ($\exists$) and normal people "there is" ("I have one"). I think this is an important distinction to be made in TCS, though. – Raphael Mar 10 at 21:13

You translated the code correctly. There are many methods for solving recurrences.

However, it is currently unknown if collatz even halts for all n; the claim that it does is known as Collatz conjecture. Therefore, no known method will work on this recurrence.

I think $T(n)$ will be $\lg n$ if $n$ is even

How so? I guess you are thinking of $n=2^k$, for which your claim is correct. This goes to show that this recurrence is not one we can solve up to $\Theta$ by investigating exponentially few points (see also here).

share|cite|improve this answer

The time complexity function is

\begin{cases} T(n)= O(1) \text{ for } n\le 1\\ T(n)=T(n/2) + O(1) \text{ for } n\text{ even}\\ T(n)=T(3n+1) + O(1)\text{ for } n\text{ odd}\\ \end{cases}

which can be rewritten as the following if you are interested in asymptotic time complexity.

\begin{cases} T(n)= 1 \text{ for } n\le 1\\ T(n)=T(n/2) + 1 \text{ for } n\text{ even}\\ T(n)=T(3n+1) + 1\text{ for } n\text{ odd}\\ \end{cases}

It is not even known that the resulting TM $\langle M,1^n\rangle \in Halt$ (See Halting Problem) for every $n$. So naturally we can't measure the time taken to halt if we do not even know if it halts for every $n$. Also refer http://math.stackexchange.com/questions/2694/what-is-the-importance-of-the-collatz-conjecture.

Collatz conjecture is a very famous conjecture which Collatz proposed in 1937. Many eminent mathematicians have spent (read wasted) countless hours in trying to solve this conjecture but to little avail. Even Paul Erdős said about the Collatz conjecture, "Mathematics is not yet ready for such problems."

share|cite|improve this answer
1  
"wasted" is a subjective judgement. see expert analysis by Lagarias for reasons why work/ partial results on the conjecture can be regarded as not "wasted". also the quote by Erdos is probably a few decades old and mathematics has progressed substantially since then, and continues to... and likely not all new mathematical techniques have been attempted against the problem. – vzn Mar 12 at 17:59
    
That was tongue in cheek comment. (To be fair I put it inside brackets, isn't it). Till the problem is solved, all the efforts seem to be wasteful, but once it is solved, you see how even the failures have led to the solution. And I don't agree with you that mathematics has progressed substantially; technology has progressed substantially, but physics, mathematics and even computer science are progressing slowly, and that is how it should be (I can say this because, I who have learnt my ropes 30 years back, still do not feel outdated). – Shreesh Mar 13 at 3:10
    
@vzn, I went and reread the introduction by Lagarias in "The Ultimate Challenge: The $3x+1$ Problem". In section 10, it kind of struck me that Lagarias seems to be more like trying to justify his position, rather than having real belief that it was effort well spent. It looks like an apologetic stand to me. Again I would say that this was my subjective feeling, because of course one cannot make such claims without knowing the person. – Shreesh Mar 13 at 12:40
    
Lagarias wrote/ compiled/ edited an entire book on the subject and it sounds "apologetic" about studying the problem? lol! quite to the contrary. however agreed/ concede he has a defensive position because a lot of other mathematicans do not consider the problem significant or worth major attack/ effort (and note gauss felt exactly the same about Fermats Last Thm!). but there are massive other cases of top mathematicians taking it totally seriously eg Tao for one. – vzn Mar 13 at 21:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.