From Turing Machines
you should be familiar with the formal model of Turing Machines (TMs):
- TMs can decide any problem solved by common programming languages.
- They are low-level representations of algorithms, which often obfuscate their underlying intuitions.
- They have well-defined cost models, in particular for measuring time and space complexity.
… To Algorithms
We will speak about algorithms and complexity more abstractly:
- We shall describe algorithms in a human-readable way, but which may theoretically be implemented by as TMs or programs.
- We refer to the number of ‘steps’ of computation, which in general will be polynomially related to time complexity in the TM model.
- We shall not worry about low-level issues such as the cost of accessing memory (cf. point above).
Time Complexity
We shall often count time complexity as the number of basic operations on the data structure at hand. Examples of such steps include:
- checking whether there is an edge between two nodes in a graph.
- checking whether the -th bit of binary string is 1 or 0
- checking (in)equality of two pieces of data
- checking that a string is a well-formed term of some grammar
- computing the sum, or even product of two natural numbers.