Tutorials

# Algorithm Performance

Every algorithm can be analyzed in terms of its performance and complexity.

The performance of an algorithm is determined by totalling the number of occurrences of each operation when algorithm is used. These performance is evaluated as a function of input size n and is to be considered modulo a multiplicative constant.

The notations that helps in determining the performance and complexity of the algorithm are:

1. Tightly bound (theta notation)
2. Upper bound (O-notation)
3. Lower bound (omega notation)

### Tightly bound

It is also known as θ-notation.

Tightly bound notation binds a function to within constant factor.

It is said f(n)=θ(g(n)) if there exists a positive constant n, c1 and c2  such that to the right of n the value of f(n) always lies between c1 g(n) and c2 g(n).

### Upper bound

It is also known as O-notation.

This notation provides an upper bound for a function to within constant factor.

It is said f(n)=O(g(n))if there exists a positive constant n and c such that to the right of n, the value of f(n) always lies on or below c g(n).

### Lower bound

It is also known as Ω-notation.

This notation provides an lower bound for a function to within constant factor.

It is said f(n)=Ω(g(n))if there exists a positive constant n and c such that to the right of n, the value of f(n) always lies on or above c g(n).

### Algorithm analysis

The algorithm is analyzed in terms of:

• Worst case complexity
• Average case compexity
• Best case complexity