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

  • $\begingroup$ How do they define $\sf DTIME$? $\endgroup$
    – A.Schulz
    May 26, 2016 at 11:33
  • $\begingroup$ 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. $\endgroup$
    – Yuval
    May 26, 2016 at 11:44

2 Answers 2


$\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).

  • 2
    $\begingroup$ So the first quote implies DTIME(n) ⊆ DTIME(2n) but not the reverse. (Aaand I make another notch in the "needless abuse of Landau notation leads to confusion" post.) $\endgroup$
    – Raphael
    May 26, 2016 at 13:40
  • 2
    $\begingroup$ 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)$. $\endgroup$
    – Bakuriu
    May 26, 2016 at 14:03
  • $\begingroup$ @Bakuriu For $c<0$? ;) But yes, I agree that that is a nicer way of putting it. $\endgroup$
    – Raphael
    May 26, 2016 at 18:47

In a purely mathematical sense, if n = 0, than DTIME(n) DOES = DTIME(2n), because 0 multiplied by any number = 0. So, if n = 0, DTIME(n) = DTIME(2n).

I dont know if this helps, but I hope it does.

  • 2
    $\begingroup$ "$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$. $\endgroup$
    – Raphael
    May 26, 2016 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.