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:


  
  start with $x=n$ for some value of $n$
  if ($x$ is odd)
  
  $x = 3x+1$
  
  else
  
  $x = \frac{x}{2}$
  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)$?
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.


Hopefully you have read Lagarias's survey before asking the question.