# 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:

- Tightly bound (theta notation)
- Upper bound (O-notation)
- 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, c_{1} and c_{2} such that to the right of n the value of f(n) always lies between c_{1} 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

**31**

Please Share this page