Why is this function computable in $O(n^{1.5})$ time?
Denote by $|x|$ the length of a number $x$, i.e. $\lfloor \log_2 x \rfloor + 1$ (for $x &gt; 0$). Calculating $2^x$ requires time $O(x)$ in the RAM model, and so calculating $f(i+1)$ from $f(i)$ takes time $O(f(i)^{1.2}) = O(|f(i+1)|)$. Since $f(i)$ is growing faster than geometrically, the overall time to calculate $f(i+1)$ is $O(|f(i+1)|)$. As you point out, you need to do so until $f(i+1) \geq n$, which means that $f(i) &lt; n$. Therefore the total running time is $O(|f(i+1)|) = O(f(i)^{1.2}) = O(n^{1.2})$.

In the Turing machine model with a single tape, calculating $2^x$ takes time $O(x\log x)$, and so the total running time is $O(n^{1.2} \log n) = O(n^{1.5})$. The algorithm for computing $2^x$ replaces $[x]$ by $1[[x]]$ (here $[x]$ is the binary representation of $x$, and $[[x]]$ is the binary representation using different digits $0',1'$), and then repeatedly runs the transformation $[[x]] \longrightarrow 0[[x-1]]$, which takes time $O(|x|) = O(\log x)$.