# Is DTIME(n) = DTIME(2n) true? (unlike Rosenberg's results)

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)?

• How do they define $\sf DTIME$? – A.Schulz May 26 '16 at 11:33
• We use on-line multitape turing machine whose input is written on one of the work tapes, DTIME(T(n)) is the set of all languages having time complexity T(n). if $L \in DTIME(T(n))$ and $L= L(M)$, that means M is determenistic turing machine and makes at most T(n) moves before halting. – Yuval May 26 '16 at 11:44

$\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).
• In my algorithmica class we 'd have defined something like $DLINTIME = \bigcup_{c < 0}{DTIME(cn)}$ and then stated the corollary as $\forall \epsilon > 0 . DLINTIME = DTIME((1+\epsilon)n)$. – Bakuriu May 26 '16 at 14:03
• @Bakuriu For $c<0$? ;) But yes, I agree that that is a nicer way of putting it. – Raphael May 26 '16 at 18:47
• "$n$" is a symbolic variable here, not something you get to insert numbers for. In particular, the whole concept of DTIME is only defined for $n \to \infty$. – Raphael May 26 '16 at 18:46