Typically, though, the number of operations required will depend on the input to the task and may vary even with inputs of the same length. As a pertinent example, say we design a computer program which tells you whether or not an integer you input is prime. If we give as input the number 256, the program will probably output 'not prime' sooner than if we had given it the number 323 (even though they both have length 9 when written as binary integers, for example), since the first integer has a very small prime factor (2) and the second has larger factors (17 and 19). Therefore we usually opt for a worst-case analysis where we record the longest running time of all inputs of a particular length. So we obtain an algebraic expression $t(n)$ that reflects the longest running time of all inputs of length $n$.
- a new state
- another symbol to write to the square it is on (though this symbol might be the same as what was already written there)
- a direction to move in: left or right.
- First put a mark on A.
- Scan all the edges of the graph. If you find an edge from a marked node to an unmarked node, mark the unmarked node.
- Repeat the above until you mark no new nodes.
- If B is marked, accept. Otherwise, reject.