The title of the question expresses what I'm looking for - this is to help me better understand the prerequisites for the Non-Deterministic Time Hierarchy Theorem

For instance, the Arora-Barak book explains the theorem using $g(n) = n$ and $G(n) = n^{1.5}$ - but, I can see that $n \in o(n^{1.5})$ as well! So, I'm trying to better understand what "extra" time is guaranteed by specifying that in order for $\text{NTIME}(g(n))$ to be a proper subset of $\text{NTIME}(G(n))$, $g(n + 1) = o(G(n))$, not $g(n) = o(G(n))$...


2 Answers 2


One example is $g(n) = 2^{2^{n-1}}$, $G(n) =2^{2^{n}}$.

We have $g(n) = \sqrt{G(n)}$, so $g(n) = o(G(n))$.

Meanwhile, of course, $g(n+1) = G(n)$ so $g(n+1) = \Theta(G(n))$, so $g(n+1)\neq o(G(n))$

Why double exponential? When we add one to $n$, we want the effect to be more than a multiplicative constant (because big $O$ notation hides multiplicative, and therefore additive constants). Let's make it simple and say that we want adding 1 to $n$ to have a polynomial effect on the value of $g(n)$. When you add a constant to $n$:

  • a linear function is increased by an additive constant

  • an exponential function is increased by a multiplicative constant

  • a double exponential function is increased polynomially (by a power of two in our example, hence $g(n)^2 = G(n)$)

We can also have $g(n) = n^n$, $g(n) = n!$, etc., where $G(n) = g(n-1)$. In general we can let $g(n) = f(n)^n$, where $f(n) = \omega(1)$ and $f$ is nondecreasing. Then we have:

$$\lim_{n\to\infty} \frac{g(n)}{G(n)} = \lim_{n\to\infty} \frac{g(n)}{g(n+1)} = \lim_{n\to\infty}\frac{f(n)^n}{f(n+1)^{n+1}} \leq \lim_{n\to\infty}\frac{f(n)^n}{f(n)^{n+1}} = \lim_{n\to\infty}\frac{1}{f(n)} = 0$$

So we've shown $g(n) = o(G(n))$ using the limit definition (the last step is because $f(n) = \omega(1)$). Therefore, functions like $(\log\log n)^n$ and even $\alpha(n)^n$ where $\alpha$ is the inverse Ackermann function, will do the trick for us as well.

  • $\begingroup$ Does anyone know of a smaller or simpler $g$, $G$ which don't use this outline but fit the requests of the OP? $\endgroup$
    – SamM
    Nov 26, 2012 at 22:26
  • 1
    $\begingroup$ $g(n)=1$ for odd $n$ and $g(n)=n$ for even $n$. $G(n)=ng(n)$. $\endgroup$
    – John L.
    Jan 19, 2020 at 19:08

Take $g(n)= n!$ and $G(n) = (n+1)!$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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