Return to 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."

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

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

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

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}

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