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