18
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ 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. $\endgroup$
    – Criticizing Israel not allowed
    Commented Mar 11, 2016 at 1:45
  • 2
    $\begingroup$ 54 is even, T(54) = 112 != lg(54) $\endgroup$
    – Taemyr
    Commented Mar 11, 2016 at 11:08
  • $\begingroup$ Is it assumed that user will only input integer? $\endgroup$
    – Dean MacGregor
    Commented Mar 11, 2016 at 15:54
  • $\begingroup$ @DeanMacGregor Yes. In fact, a positive integer is assumed. $\endgroup$
    – user29110
    Commented Mar 12, 2016 at 0:28
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Commented Mar 12, 2016 at 17:55

5 Answers 5

Reset to default
31
$\begingroup$

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

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks. But my recursion is true right? If so, then we still cannot find the solution for that recursion? $\endgroup$
    – 9bi7
    Commented Mar 10, 2016 at 18:44
  • $\begingroup$ 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. $\endgroup$
    – Evil
    Commented Mar 10, 2016 at 18:55
  • $\begingroup$ 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? $\endgroup$
    – 9bi7
    Commented Mar 10, 2016 at 19:26
  • 7
    $\begingroup$ "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. $\endgroup$
    – Raphael
    Commented Mar 10, 2016 at 21:05
  • 7
    $\begingroup$ 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. $\endgroup$
    – Raphael
    Commented Mar 10, 2016 at 21:13
15
$\begingroup$

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

Improve this answer
$\endgroup$
13
$\begingroup$

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 https://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."

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ "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. $\endgroup$
    – vzn
    Commented Mar 12, 2016 at 17:59
  • $\begingroup$ 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). $\endgroup$
    – Sarvottamananda
    Commented Mar 13, 2016 at 3:10
  • $\begingroup$ @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. $\endgroup$
    – Sarvottamananda
    Commented Mar 13, 2016 at 12:40
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Commented Mar 13, 2016 at 21:44
2
$\begingroup$

I would add to the other answers the fact that the third branch of the function i.e the case of $n$ is $odd$ suggests that in that case the function will be computed on a larger instance ($n$ is lower than $3n+1$). So there is more work to be done on that computation branch.

Other recurrence relations that we encounter (for example in the case of merge sort $T(n) = 2T(n/2) +n$) adhere to the division of a problem into subproblems for instances with smaller size. Those reccurences degenerate naturally into base case(s), namely $T(0)$ or $T(1)$ which are known. So, standard mathematical tools for analyzing the reccurence can be used, like the master theorem.

In the case of collatz function we are not able to infer directly from the reccurence that the case of $3n+1$ will eventually deteriorate using standard mathematical tools of reccurences. This is a topic to be resolved by looking at the problem itself, not the reccurence that describes it.

Improve this answer
$\endgroup$
0
$\begingroup$

You have T (n) = T (n/2) + 1 if n is even. But then n/2 is quite likely not even, so you are stuck there.

What happens is that the nice little rules that you learned are confronted with a real problem, and they don't work. They hit a brick wall, face first, and it hurts. Do yourself a favour, and follow the recursion for T (7) manually, and then you tells if you still believe this is related lg n.

If you think this isn't related to the original question because 7 is not even: Whenever n is odd, T (n) = T (3n + 1), and 3n + 1 is even, so if T (n) were log n if n is even, it would be log (3n + 1) + 1 whenever n > 1 is odd.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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