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?


1 Answer 1


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.

  • $\begingroup$ 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)$? $\endgroup$
    – Bedivere
    Commented Oct 4, 2022 at 10:51
  • $\begingroup$ 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"? $\endgroup$
    – Bedivere
    Commented Oct 4, 2022 at 10:56
  • $\begingroup$ 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. $\endgroup$ Commented Oct 5, 2022 at 19:25

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.