Time Complexity

complexity-theory

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 $I$, let

$$m(I)=|I|$$

be the number of symbols in the encoded input. The worst-case time complexity of an algorithm $A$ is the function

$$T_A(n)=\max \{{\mathrm{time}}_A(I)\mid |I|=n\}.$$

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 $W$ written in binary has length $\Theta (\log W)$, while the same number written in unary has length $\Theta (W)$.

This matters because an algorithm that loops over all values $0,1,\dots ,W$ performs $\Theta (W)$ iterations. Under binary encoding, this can be exponential in the input length. Under unary encoding, it is polynomial in the input length.

Polynomial Bound

An algorithm runs in polynomial time if there exist fixed constants $C,c$ such that, for every instance $I$,

$${\mathrm{time}}_A(I)\le C\cdot |I{|}^c.$$

The exponent $c$ is fixed for the algorithm. It cannot depend on the instance.

Examples

Addition remains polynomial

Consider the algorithm that adds two non-negative integers $x$ and $y$ using the usual digit-by-digit addition procedure.

If $x$ and $y$ are encoded in binary, the input length is

$$m_{\text{bin}}=\Theta (\log x+\log y),$$

and the algorithm runs in $O(m_{\text{bin}})$ time, since it processes each bit at most constantly many times.

If $x$ and $y$ are encoded in unary, the input length is

$$m_{\text{unary}}=\Theta (x+y),$$

and the same task can be done in $O(m_{\text{unary}})$ 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 $0,1,\dots ,x$. It only processes the symbols that are already present in the input.

Knapsack depends on the encoding

Let $n$ be the number of items and let $W$ be the knapsack capacity. The standard knapsack dynamic programme has running time $O(nW)$.

If $W$ is encoded in binary, its bit-length is ${\ell }_W(I)=\lceil {\log }_2(W+1)\rceil$. For instances with $W=2^L$, the capacity field needs only $L+1$ bits, but the algorithm still iterates over all values $0,1,\dots ,W$. Hence

$$O(nW)=O(n{2}^L),$$

which is exponential in the binary length $L$ of the capacity.

If $W$ is encoded in unary, then the input length already contains $\Theta (W)$ symbols for the capacity. The same running time $O(nW)$ is then polynomial in the input length.

Thus this dynamic programme is polynomial under unary encoding but pseudo-polynomial under binary encoding.