Time complexity versus space complexity in Turing machines

Question

I think defenitions of time complexity and space complexity for Turing machines are identical and I can't differentiate between them.

Please help me. Thanks.

Solution 1

With regards to a Turing machine, time complexity is a measure of how many times the tape moves when the machine is started on some input. Space complexity refers to how many cells of the tape are written to when the machine runs.

The time complexity of a TM is connected to its space complexity. In particular, if tue space complexity of a TM is f(w) for input w, then its time complexity must be at least f(w), since the tape has to move at least f(w) steps to write out that many cells. Additionally, if the TM has tape alphabet Γ and set of states Q, then if the space complexity of the TM on an input w is f(w) and the TM halts on w, the time complexity must be at most |Q|Γ^f(n). To see this, note that the configuration of the TM at any point in its execution consists of a string of f(n) tape cells, each of which can contain any tape symbol, and can be in one of any of its |Q| states.

An interesting example of this distinction appears if you look at restricted Turing machines like the linear bounded automaton (LBA), a Turing machine that has its tape restricted to space proportional to the size of the input. Although the TM's space complexity is restricted to O(n), the time complexity of any particular LBA can be exponential in the size of the input.

Hope this helps!

Solution 2

Time complexity is the measure of how long the algorithm takes to produce an answer.

Space complexity is the measure of how of much memory the algorithm uses in the process.

As an example, consider the problem of computing the sum of the integers 1..n. A simple algorithm would work something like:

procedure sum(n)
  total := 0
  for i = 1 to n
    total := total + a[n]
  return total

The time complexity of this algorithm is O(n) because the loop clearly goes through n iterations. On the other hand, the space complexity is O(1) because the only memory we need is for total and i, which are independent of n.

Comments

[amir amir]

My mean is about Turing Machine not general defenition of space and time complexity. please explain me in this context !

[Mitch Wheat]

if your question was about a turing machine why didn't you mention it in your question?

[Peter Alexander]

The definitions don't really change. For the Turing machine, time is just a measure of the number of state changes before halting, and the space complexity is just the number of tape cells used.

[amir amir]

Oh , This is that things I want . Please explain more .

[Peter Alexander]

@amir amir: What else do you want to know? I believe I've explained it as much as possible. If you do not understand what a Turing machine is, or what complexity is in general then please search this site for an answer to those questions, and ask if you can't find anything.

[amir amir]

thanks , Do you mean that Space complexity counts number of cells in the tape of turing machine that they are not empty ? and Do you mean that Time Complexity counts number of head movement ?

[templatetypedef]

Space complexity is the total number of cells that the head ever reads, including cells read or written to that contain blanks. Note that the machine actually needs to scan the cell, though. And yes, time complexity is the total number of times that the tape head moves.

[amir amir]

thanks , for example if head go 4 cells right and then come 3 cells left Do we add 7 step to space complexity or Do we add 1 step to space complexity ?

[templatetypedef]

The space complexity would grow by four, since you scanned four new cells. The three you backtracked over don't contribute anything new because the space was already used.

[cuppajoeman]

What does n represent in here?

[templatetypedef]

@cuppajoeman Typically in TM Land n refers to the length of the input in characters.