What is the difference between “DTIME” and “Big O” notation?

Question

I have some understanding of "big O" and "little O" notation. I have heard of "DTIME" but have not had formal education or training regarding its use. Can someone explain the difference (or relationship, if this is apples and oranges) of "big O" (or "little O" or similar) notation and "DTIME"?

Wikipedia defines "DTIME" as "the amount of time (or number of computation steps) that a "normal" physical computer would take to solve a certain computational problem using a certain algorithm." (http://en.wikipedia.org/wiki/DTIME).

Wikipedia defines "Big O" as "the limiting behavior of a function when the argument tends towards a particular value or infinity" (http://en.wikipedia.org/wiki/Big_O_notation).

Neither page makes reference to the other. The page on time complexity (http://en.wikipedia.org/wiki/Time_complexity) mentions both but not in relation to each other or by way of comparison or definition. To hazard a guess: is the difference the nature of the input? That is, "big O" and "little O" describe output given a (asymptotic) range of input, whereas "DTIME" describes output of a single input?

Answer 1

• DTime: is a the set of time complexity classes for problems. It relates to running on a turing machine. The complexitity class e.g. P includes all problems that are solvable in polynomial time on a turing maschine (you can think of P as a higher boundary).
• Big O: This is a measure that can be used to measure the asymptotic performance of an algorithm. $O(n^c),c>1$ says that for the input size $n$ the related asymptotic performance will be polynomial.

Conslusion: Given a problem that is complexity class P $=>$ the optimal algorithm for this problem should have $O(n^c),c>1$. Bear in mind that the problem is a decision problem.

Feel free to correct me, if i'm wrong!