[Solved]: Is DTIME(n) = DTIME(2n) true? (unlike Rosenberg's results)

Problem Detail: 

I'm reading Homer and Selman's "Computability and Complexity" book. In some Corollary 5.3 it says:

For all ε‎ > 0, DTIME(O(n)) = DTIME( (1+ε‎‎) n).

Now I'm confused with this corollary and Rosenberg's result (p87 in the same book):

DTIME(n) ≠ DTIME(2n).

Why can we not use the corollary to show that DTIME(n) = DTIME(2n)?

Asked By : math

Answered By : Gro-Tsen

$\mathrm{DTIME}(O(n))$ is the set of problems that can be solved in deterministic $O(n)$ time for some constant implicit in $O$, in other words, it is the union of the $\mathrm{DTIME}(cn)$ for all $c>0$. That this union is, in fact, equal to $\mathrm{DTIME}(cn)$ for any given $c>1$ (i.e., $1+\varepsilon$) means that all the $\mathrm{DTIME}(cn)$ for $c>1$ are equal, it does not say anything about $\mathrm{DTIME}(n)$, so there is no contradiction with the fact that $\mathrm{DTIME}(n)\neq \mathrm{DTIME}(2n)$ (although the results could have been stated in a clearer way).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/57889