# Two functions $g(n)$, $G(n)$ such that $g(n) = o(G(n))$ but $g(n+1) \neq o(G(n))$

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))$...

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.

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

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