# Meaning of the Time Hierarchy Theorem

Given two positive integers $c_1$ and $c_2$ such that $c_1 < c_2$, it's easy to prove that $n^{c_1}$ is $\mathcal{O}(n^{c_2})$ while $n^{c_2}$ is not $\mathcal{O}(n^{c_1})$. In general, for any functions $f(n)$ and $g(n)$ it is possible to determine which one (or both) is true, $f \in \mathcal{O}(g)$ or $g \in \mathcal{O}(f)$ using only definition of big-O notation. Thus it is not hard to see that TIME($n^{c_1}) \subsetneq$ TIME($n^{c_2})$ without using the Time Hierarchy theorem.

So, what is the meaning of the Time Hierarchy theorem and how and where can I use it?

You miss the meaning of the Time Hierarchy theorem, or perhaps of the classes TIME($n^k$) that you show.
It is indeed obvious that $O(n^k) \subsetneq O(n^{k+1})$, for instance. It is also clear that the set of Turing machines that run in time $O(n^k)$ is a strict subset of those that run in $O(n^{k+1})$.
However, it is not immediately obvious that the set of problems that can be solved by TMs in time $O(n^k)$ (i.e., the class TIME($n^k$)) is a strict subset of TIME($n^{k+1})$. For this much stronger statement, you need the Time Hierarchy Theorem. That is, you need to argue that there exists some problem that can be solved in time $n^{k+1}$ but not in time $n^k$. (Of course, this is just a special case of applying the theorem to polynomial running times.)
• Thanks for clarification. Now I understand, big-O is used for classifications functions and Turing machines, while TIME($.$) is a problem class. That was the key point. – B.K. Dec 9 '17 at 14:46