Definition
Time Complexity
The time complexity of an algorithm is a function that bounds its runtime in terms of the length of the encoded input.
Formally, fix an encoding of problem instances. For an instance
, let be the number of symbols in the encoded input. The worst-case time complexity of an algorithm
is the function Thus, time complexity measures how the number of computation steps grows as the encoded input length grows.
Encoding
Time complexity is measured relative to an encoding. The relevant size is not the semantic value of the input, but the number of symbols needed to write it down.
For example, a number
This matters because an algorithm that loops over all values
Polynomial Bound
An algorithm runs in polynomial time if there exist fixed constants
The exponent
Examples
Addition remains polynomial
Consider the algorithm that adds two non-negative integers
and using the usual digit-by-digit addition procedure. If
and are encoded in binary, the input length is and the algorithm runs in
time, since it processes each bit at most constantly many times. If
and are encoded in unary, the input length is and the same task can be done in
time by scanning the input. Thus addition is polynomial under both encodings. The reason is that the algorithm does not expand a compact number into all values
. It only processes the symbols that are already present in the input.
Knapsack depends on the encoding
Let
be the number of items and let be the knapsack capacity. The standard knapsack dynamic programme has running time . If
is encoded in binary, its bit-length is . For instances with , the capacity field needs only bits, but the algorithm still iterates over all values . Hence which is exponential in the binary length
of the capacity. If
is encoded in unary, then the input length already contains symbols for the capacity. The same running time is then polynomial in the input length. Thus this dynamic programme is polynomial under unary encoding but pseudo-polynomial under binary encoding.