19
$\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$ Commented Mar 11, 2016 at 1:45
  • 2
    $\begingroup$ 54 is even, T(54) = 112 != lg(54) $\endgroup$ Commented Mar 11, 2016 at 11:08
  • $\begingroup$ Is it assumed that user will only input integer? $\endgroup$ Commented Mar 11, 2016 at 15:54
  • $\begingroup$ @DeanMacGregor Yes. In fact, a positive integer is assumed. $\endgroup$ 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$ 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$ 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$ 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$ 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$ 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$ 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$ 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$ 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$ 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$ 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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.