My textbook says: "We define the function $f\colon \mathbb{N}\to\mathbb{N}$ as follows: $f(1)=2$ and $f(i+1)=2^{f(i)^{1.2}}$. Note that given $n$, we can easily find in $O(n^{1.5})$ time the number $i$ such that $n$ is sandwiched between $f(i)$ and $f(i+1)$."

How can I convince myself that we can in fact easily find $i$ in $O(n^{1.5})$ time? As $f$ is defined recursively, I think we have to compute $f(1),f(2),f(3)\dots f(j)$ until $f(j)\geq n$. In order to find out the time that these computations take, I think we have to find a suitable upper bound for $i$ dependent on $n$ and we have to find an upper bound on the execution time of the function $x\to2^{x^{1.2}}$. In the end, we can hopefully show the quoted proposition. Unfortunately, I don't see neither one thing nor the other.

I forgot to mention: Please note that we are in a nondeterministic context. So $f$ is claimed to be computable in $O(n^{1.5})$ by a nondeterministic Turing machine.

As quite a few people have already read this question, with some of them finding it useful and interesting too, but nobody answered so far, I want to provide some more information on the context: The quoted claim is an integral part of the proof of the nondeterministic time hierarchy theorem. The proof (with the claim) can be found e. g. in the book by Arora and Barak, but I have found quite a few other resources on the Web too which present the same proof. Each of those calls the claim easy or trivial and does not elaborate on how to find $i$ in $O(n^{1.5})$ time. So either all these resources just copied from Arora and Barak or the claim is in fact not so difficult.

  • 1
    $\begingroup$ This looks like the nondeterministic time hierarchy theorem proof in Arora & Barak, is it? If so, I assume nondeterminism plays a role here. $\endgroup$ – G. Bach Feb 14 '14 at 16:48
  • $\begingroup$ You're right. Sorry for that, I should have mentioned the nondeterministic context. Can you please explain in more detail how nondeterminism helps us there to show the O(n^1.5) bound? $\endgroup$ – user1494080 Feb 14 '14 at 17:01

Denote by $|x|$ the length of a number $x$, i.e. $\lfloor \log_2 x \rfloor + 1$ (for $x > 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) < 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)$.

  • $\begingroup$ Perfect, thanks! One more question: Don’t we have to argue that |f(i)| grows faster than geometrically rather than that f(i) grows faster than geometrically? $\endgroup$ – user1494080 Feb 15 '14 at 13:34
  • $\begingroup$ Since $|f(i+1)| = f(i)^{1.2}$, it's the same thing, but you're right. What we really want is $\sum_{j \leq i} |f(j)| = O(|f(i)|)$. $\endgroup$ – Yuval Filmus Feb 15 '14 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.