# What is the asymptotic time complexity of the number of steps of “Half Or Triple Plus One” ( HOTPO)?

The "Half Or Triple Plus One" process goes as follows:

1. start with $x=n$ for some value of $n$
2. if ($x$ is odd)

$x = 3x+1$

else

$x = \frac{x}{2}$

3. if ($x$ > 1) goto (2)

Define $f(n) =$

total stopping time of $n$, i.e. The number of steps required for the procedure to halt.


The Collatz conjecture suggests that the process stops for every value of $n$, hence if the conjecture holds, $f$ is well defined.

The question is:

What is the asymptotic time complexity of calculating $f(n)$?

• How is $f(n) = \Theta(n)$ not obvious? – Sasho Nikolov Aug 3 '14 at 8:17
• There is no known explicit bound on the complexity of f, and proving one would go a long way towards solving the conjecture. – Emil Jeřábek supports Monica Aug 3 '14 at 10:45
• Just to make clear, my first comment was for a completely different $f(n)$ (or at least the way I understood it). – Sasho Nikolov Aug 3 '14 at 15:08
• BTW there are results of the type $\Omega(n^c)$ of the numbers in $\{1, \ldots, n\}$ have finite stopping time, for $c < 1$ a fixed constant. If that's of interest I can find the citation. – Sasho Nikolov Aug 4 '14 at 15:45
• @SashoNikolov I'd love to see some of these results! – Alexis Petrounias Aug 5 '14 at 13:01

First, as the conjecture is still open, we can't say if $f$ is even defined for every $n$.

Let's assume that if $f(n)=\infty$, then the algorithm is required to output $-1$.

In 1972 Conway showed that a generalization of the problem of determining whether $f(n)= \infty$ is undecidable. In particular, no algorithm can always determine, on input $n$ and sequences $(a_i)_{i=0}^{p-1}$, $(b_i)_{i=0}^{p-1}$, whether the process that starts with $x = n$ and iteratively maps $x$ to $a_ix + b_i$ whenever $x \equiv i \pmod{p}$ terminates at 1 in finite time. Here the $a_i$ and $b_i$ are assumed to be chosen so that the results are always integers. This result isn't necessarily applicable for the Collatz function, which presents only one fixed choice of $a_i$ and $b_i$ and leaves only $n$ as a variable.

Side note: The A006877 series in http://oeis.org/ contains the values of $n$ for which $\forall m<n:f(m)<f(n)$.

• Does Conway's result imply we cannot provide a complexity measure of f(n)? Could we provide a probabilistic measure for ranges of n? – Alexis Petrounias Aug 3 '14 at 10:17
• If the finiteness of $f(n)$ is undecidable, then $f(n)$ is not bounded by any recursive function. However, Conway's result does not apply to this particular f, but to a more general class of similar functions. – Emil Jeřábek supports Monica Aug 3 '14 at 10:41
• RB, can you edit your answer to make clear the Conway has not shown undecidablity for the Collatz function, but for a related more general class of functions. – Sasho Nikolov Aug 3 '14 at 15:11
• any proof/evidence that the Collatz problem itself has some aspect of undecidability embedded in it would be a theoretical breakthrough... – vzn Aug 4 '14 at 21:46

By request, two facts that are known and seem somewhat related to your question.

• As a lower bound: infinitely many integers $n$ take time $\Omega(\log n)$. Applegate and Lagarias.

• As a sort of an upper bound: $\Omega(N^c)$ positive integers bounded by $N$ reach $1$ in finite time, where $c \approx 0.84$. Krasikov and Lagarias.