algorithmcomplexity-theorytime-complexityturing-machinesspace-complexity# Time complexity versus space complexity in Turing machines

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

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!

- How to generate uniformly distributed subintervals of an interval?
- Generating random number in a non-power-of-2 range from random bits
- Algorithm - Search and Replace a string
- Looking for a branchless algorithm for converting a specific set of 4-bit integers
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Find four,whose sum equals to target
- A* algorithm can't find the goal in Python
- Efficiently getting all divisors of a given number
- Are there any existed API to split IEnumerable<T> to many Vector<T> in CSharp？
- Generating all divisors of a number given its prime factorization
- Efficient way to insert a number into a sorted array of numbers?
- BFS Maximize Minimum Distance from a Monster along a path
- Is there effective algorithm that will return all different combination?
- Big O of algorithm that steps over array recursively
- Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity
- Traversing/Moving over an unfolded cube
- Fibonacci Recursion using Golden Ratio(Golden Number)
- Karatsuba implementation in C
- Why is O(n) better than O( nlog(n) )?
- What is Sliding Window Algorithm? Examples?
- How to write a function to navigate through a non-binary tree?
- Evenly distribute QDate values into certain number of slots
- Find max product using divide and conqure in O(n) time
- Cache-friendly sqare matrix transposition logic issue
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Fast Convertion From Adjacency List to Edge List
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Reversing the word order in a string in place
- Trying to make a 2x2 rubik's cube solving algorithm , how do i find the solution path (DFS)?
- question about missing element in array