A Few Words On Algorithm Complexity

One of the key properties of a given algorithm is its complexity. A computer scientist is interested in the adequacy of the algorithm runtime relative to the size of the input. While there exist sharp runtime lower bounds for any given algorithm, for upper bounds however, the sky is the limit. It depends on the quality of optimization.

A Formality Of Runtime Complexity

When talking about runtimes, the complexity is described in “buckets of algorithms” with a similar runtime. This is the so-called “O-Notation”. Formally, it looks like this.

    \begin{align*}{A(n) \in \mathcal{O}\left(f\left(n\right)\right) \Leftrightarrow \exists c,n_0\in\mathbb{R}_+. A(n) \leq c\cdot f(n) ~ \forall n \geq n_0 }\end{align*}

An algorithm A with input of size n is in \mathcal{O}\left(f\left(n\right)\right) (this is the O-notation), when there exists a cofactor c and a starting size n_0 out of \mathbb{R} such that c \cdot f(n) dominates A(n) for all input sizes greater than n_0. In other words, it means that we try to “cap” the runtime with an upper bound function f.

Take a look at the following list of popular runtimes:

Highly Recurrent Runtimes

Consider writing a searching algorithm for an element in a list of size n. You then would iterate over the list indices and compare if the element is on the respective position.

If the element is found, then return the index, else carry on. This means that we iterate over the whole list (\mathcal{O}(n)) and compare if the element is found (\mathcal{O}(1)). The total runtime values \mathcal{O}(n) \cdot  \mathcal{O}(1) =  \mathcal{O}(n).
You could state that the runtime of this algorithm is a quadratic one ( \mathcal{O}(n^2)) and, you wouldn’t be technically wrong! Everything that can be described with a linear function can be bounded with a quadratic function but in terms of adequacy this would not be appropriate.

Of course, just because an algorithm might run in an expected runtime, does not mean that it actually does run in the runtime. For example, almost every comparison-based sorting algorithm terminates after a linear amount of steps when the input array is already sorted. But, this is a special scenario, it’s not the standard case.

In application, it might not seem straight-forward to determine the runtime for algorithm analysis. An algorithm might be composed of multiple sub-algorithms and it is not clear how frequently those sub-algorithms are being called or how they depend on each other. Bringing more ambiguity into this topic, a worst case runtime of an algorithm is not always a sharp upper bound. For example, what if the normal case is in constant time and the worst case in linear time, but only occuring every \log n-th step? This issue is served by the so-called amortized analysis.

Have a good day 🙂

References

https://de.wikipedia.org/wiki/Landau-Symbole