# Show that $TIME(\sqrt{n})$ = $TIME(1)$

Also known as CMU 15-455, Spring 2017, Homework 2.4.

Before I ask the main questions, let me first give a sketch of my idea. First, recall the definition of big-$$O$$ and time complexity class $$TIME(t(n))$$.

• Definition: Let $$f$$ and $$g$$ be functions $$f$$, $$g$$: $$\mathbb{N}$$ $$\rightarrow$$ $$\mathbb{R}^+$$. Say that $$f(n)$$ = $$O(g(n))$$ if $$\lim_{n \to \infty}\dfrac{f(n)}{g(n)}$$ = 0. In other words, $$f(n) = O(g(n))$$ means that for any real number $$c$$ > 0, a number $$n_0$$ exists, where $$f(n)$$ $$\leq$$ $$cg(n)$$ for all $$n \geq n_0$$.

• Definition: Let $$t: \mathbb{N} \rightarrow \mathbb{R}^+$$ be a function. Define the time complexity class, $$TIME(t(n))$$, to be the collection of all languages that are decidable by an $$O(t(n))$$ time Turing machine.

By definition, $$TIME(\sqrt{n})$$ and $$TIME(1)$$ are the collection of all languages that are decidable by a $$O(\sqrt{n})$$ and a $$O(1)$$ time TM respectively. My approach is the following:

Proposition: $$TIME(1)$$ is the collection of all languages that are decidable by an $$O(\sqrt{n})$$ time Turing machine.

If the above proposition is true, it should be sufficient to prove that $$TIME(\sqrt{n})$$ = $$TIME(1)$$. If the runtime is a constant $$c$$, then we can use the runtime $$O(1)$$ to represent $$c$$. Let $$c = 1$$ as an example. Obviously, $$1$$ = $$O(1)$$. We wish to show that $$1$$ = $$O(\sqrt{n})$$ as well.

By the definition of big-$$O$$, we have to prove that $$\lim_{n\to\infty} \dfrac{1}{\sqrt{n}} = 0$$, which is true. As such, $$1$$ = $$O(1)$$ = $$O(\sqrt{n})$$. As $$TIME(1)$$ is the collection of all languages that are decidable by an $$O(1)$$ time TM, and $$O(1)$$ = $$O(\sqrt{n})$$, the above proposition is proved. Hence $$TIME(\sqrt{n})$$ = $$TIME(1)$$.

The proof looks sound to me. However, upon further inspection, I have some problems with it:

1. The reverse approach, $$TIME(\sqrt{n})$$ is the collection of all languages decidable by an $$O(1)$$ time TM does not seem to work. Because if I understand the definition of big-$$O$$ correctly, are we trying to assert that $$\sqrt{n}$$ = $$O(\sqrt{n})$$ = $$O(1)$$? Then $$\sqrt{n}$$ = $$1$$, which is not true? What did I get wrong?

2. How can we show that $$1 = O(1)$$ with the definition of big-$$O$$ above? $$\lim_{n\to\infty} \dfrac{1}{1} = 1 \neq 0$$. And if we use the second version of the definition, what if $$0 \leq c \leq 1$$?

Those are my main question. In the case my approach is wrong, how will you approach it?

Suppose that a Turing machine runs in time at most $$T(n)$$ on inputs of length $$n$$, where $$T(n) = o(n)$$. Therefore $$\lim_{n\to\infty} T(n)/n = 0$$, and so we can find $$N$$ such that $$T(n) < n$$ for $$n \geq N$$.
Let $$x$$ be an input of size at least $$N$$, and let $$y$$ be the first $$N$$ symbols of $$x$$. If we run the Turing machine on $$y$$ then it halts in fewer than $$N$$ steps, and in particular, it doesn't reach end of the input. Therefore the Turing machine behaves exactly the same on $$x$$ and on $$y$$, and consequently, the running time on $$x$$ is also at most $$T(N)$$. Therefore the Turing machine halts on all inputs in time at most $$\max(T(1),\ldots,T(N))$$.
If instead of a Turing machine we had a random-access machine, then running times smaller than the input length do make sense. In such a setting, machines running in time $$O(\sqrt{n})$$ are indeed more powerful than those running in constant time.
• I think you are onto something, but I can't fully grasp your answer yet. I have a few questions to ask, which I hope you don't mind. 1. You are saying that given input $y$ of size $N$, and a TM running in time at most $T(n) = o(n)$, this TM halts in fewer than $N$ steps. Is it because you can always find $N$ such that $T(n) < n$ for $n \geq N$, and you let $n = N$? 2. How does $max(T(1),.., T(N))$ function? Does it take the time complexity class decidable by a TM with the smallest running time? Like you put $max(1, \sqrt{n})$ and it outputs 1, thus show that $TIME(\sqrt{n}) = TIME(1)$? Commented Oct 4, 2022 at 10:51
• 3. What is the difference between a TM and a random-access machine? Is it that TM has to iterate through each consecutive cell, while a random-access machine can jump between two cells that are far away? 4. How does the last paragraph relate to the problem I am asking? When you say $O(\sqrt{n})$ time machine are stronger than $O(1)$ time machine, is this only referring to random-access machine? And what does it mean for a machine to be "more powerful"? Commented Oct 4, 2022 at 10:56
• 1. This is not what I am saying, and isn't true. I'm saying that for large $n$, we have $T(n) < n$. This could fail for small $n$. 2. This is the maximal value among $T(1),\ldots,T(N)$. 3. A random-access machine us the implicit machine model used when describing algorithms in textbooks on algorithms. 4. Random-access machines running in time $O(\sqrt{n})$ can solve problems which random-access machines running in time $O(1)$ cannot. Commented Oct 5, 2022 at 19:25