# Asymptotic complexity of algorithms

## Contents

## Asymptotic complexity vs. run time

- Roughly speaking, the run time of an algorithm is measured by the number of operations executed by the machine.
- However, in theoretical considerations, the run time is estimated by the algorithm's
**asymptotic complexity**. In asymptotic considerations, constant multiplicative factors are completely disregarded. For that, it does not matter how fast the machine and how smart the algorithm's implementation is.

## Characterizing parameters

For the inputs of an algorithmic problem, one or more (numerical) **characterizing parameters** are to be selected, from which the total size of an input can be computed (or, at least, quite tightly bounded from above and from below).

**Examples:**

- The number of elements in sets, maps, and sequences and the (maximum) size of an element in a set, map, or sequence.
- The number of nodes and the number of edges/arcs in a graph.

## Asymptotic complexity of an algorithm

- For a selection of characterizing parameters for an algorithmic problem, let denote the set of all instances for which these parameters assume the values .
- For an algorithm for this algorithmic problem, the
**asymptotic complexity**of the algorithm with respect to this selection of characterizing parameters is defined as follows.- In the
**worst case**: by the function such that is the*maximum*number of operations executed by the algorithm for any instance in . - In the
**best case**: by the function such that is the*minimum*number of operations executed by the algorithm for any instance in . - In the
**average case**: For this case, a probability distribution over each set is required. For short, let . Then the asymptotic average complexity is the function such that is the*expected*number of operations executed by the algorithm, taken over all instances in , with respect to the distribution .

- In the

## Bounds on the asymtptotic complexity

Consider an algorithmic problem, a selection of characteristizing parameters, and an algorithm for this algorithmic problem. Moreover, let , , and be defined as above.

For a function , we say that the algorithm's complexity (the algorithm, for short) is in

- in the worst case, if ,
- in the best case, if ,
- in the average case with respect to , if ,

where "" is one of "", "", "", and "".

## Asymptotic complexity analysis of an algorithm

An asymptotic complexity analysis of an algorithm combines two aspects: (1) which case (worst, best, average) is to be analyzed and (2) which type of function class (, , , ) is to be determined. Note that the case and the function class are two separate concepts, which are easily confused.