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?

(I have asked this question on the Computer Science Stack Exchange, but no one has given an answer yet. I figure asking here may get more responses, since the question is also math-oriented.)

Bedivere
  • 81
  • Are you working on the book "Introduction to the Theory of Computation" by M. Sipser ? In this case, why do you give instead the cryptic "CMU 15-455" reference ? – Jean Marie Oct 01 '22 at 08:11
  • I was following the undergrad caught taught at CMU called Undergrad Complexity Theory, which is also referenced as CS 15-455. You can check it out here: https://www.cs.cmu.edu/~odonnell/15455-s17/ – Bedivere Oct 01 '22 at 08:30
  • But what is behind the acronym CMU ? It is not known in remote countries like my one... – Jean Marie Oct 01 '22 at 08:37
  • It's Carnegie Mellon University. It is quite famous, enough that I have heard of it even though I do not study there. – Bedivere Oct 01 '22 at 08:48

1 Answers1

6

$f(n)=O(g(n))$ is a dangerous notation. It isn't what it looks like. It really means $f(n)\in O(g(n)),$ that is, $f(n)$ is among the functions that belong to the class $O(g(n))$ (which is defined a little differently than what you wrote). It doesn't even follow the most basic properties of the $=$ relation, such as that if $a=b$ then $b=a,$ but people use this notation anyway because that's how they learned it.

It is true that if $g(n)<h(n)$ for all positive $n$ then any function that is in $O(g(n))$ is in $O(h(n))$ -- but the converse is not true. You found that any member of $TIME(1)$ is also a member of $TIME(\sqrt n)$, but as you noticed, that is not the same thing as showing that any member of $TIME(\sqrt n)$ is a member of $TIME(1)$.

If you could prove both directions you would prove that the classes are equal, but if you can show the existence of even one language that is in $TIME(\sqrt n)$ and not in $TIME(1)$ you would prove that the classes are not equal.

Some of your confusion is due to incorrect statements of definitions. The first "big-O" definition you gave is actually a definition of "little-O", $f(n) \in o(g(n)).$ In the second definition (which is almost the "big-O" definition), there just needs to exist some $c$ for which the rest is true; you do not need the rest of the statement to be true for every positive $c.$

David K
  • 98,388
  • I see your points. But do you think that my ideas are on the right track? I.e. is it possible to show that any member of $TIME(\sqrt{n})$ is a member of $TIME(1)$?

    As for the definition of big-O, Sipser's book only mentions small-$o$ notation and say that big-$O$ is the $\leq$ equivalent of small-$o$ (the $<$ version), without formally stating it. So thank you for pointing that out.

     – Bedivere Oct 01 '22 at 05:29
  • 2
    You would need to prove that there are no languages that are decidable in time proportional to $\sqrt n$ that cannot be decided in constant time. – David K Oct 01 '22 at 05:36
  • As for the first formal definition of Big-$O$ (the one using limit), what is wrong with it? Is limit not sufficient to describe Big-$O$? – Bedivere Oct 01 '22 at 05:48
  • 1
    The first definition is literally little-O. I don't think you can use a limit to define big-O. – David K Oct 01 '22 at 06:01
  • As for the "converse is not true", are you saying that $g(n) > h(n)$ does not imply that any function in $O(g(n))$ is in $O(h(n))$? – Bedivere Oct 01 '22 at 06:57
  • That's right, for example $g(n)=n^2+1>h(n)=1$ does not imply that $O(n^2+1)$ is contained in $O(1).$ In fact $g(n)=n^2+1$ itself is a function in $O(n^2+1)$ but is not in $O(1).$ – David K Oct 01 '22 at 14:59