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.

Rico

simple wiki search would answer your question. – Volans

I searched but I don't understand! – Rico

Answer 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 f(n)|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 with the tape head in any of the f(n) positions.

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!

Ready

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 ? – Rico

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. – Ready

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 ? – Rico

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. – Ready

What does n represent in here? – Booster

@Booster Typically in TM Land n refers to the length of the input in characters. – Ready

According to my prof's slides, the upper bound for the time complexity is f(n) * |Q| * |Γ|^f(n), where the f(n) multiplier accounts for possible head positions. Is there a reason this factor is missing in your answer? – Matrix

Answer 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.

Amylaceous

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

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

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. – Amylaceous

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

@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. – Amylaceous