Asymptotic Notations

These notations are used to describe the Running time of an algorithm, in terms of functions, whose domains are the set of natural numbers, N = {1, 2, ……}. Such notations are convenient for describing the worst case running time function. T(n) (problem size input size). The complexity function can be also be used to compare two algorithms P and Q that perform the same task. The basic Asymptotic Notations are:

1. O(Big-”Oh”) Notation. [Maximum number of steps to solve a problem, (upper bound)]
2. Ω (Big-”Omega”) Notation [Minimum number of steps to solve a problem, (lower bound)]
3. θ (Theta) Notation [Average number of steps to solve a problem, (used to express both upper and lower bound of a given )f(n)).

The Notation O (BIG ‘Oh’)

Big ‘Oh’ Notation is used to express an asymptotic upper bound (maximum steps) for a given function f(n). Let f(n) and g(n) are two positive functions, each from the set of natural numbers (domain) to the positive real numbers.

We say that the function f(n) = O (g(n)) [read as “f of n is big “Oh” of g of n”], if there exist two positive constants C and N0 such that

The intuition behind O-notation is shown in figure-1

Fig. 1

For all values of n to the right of n0, the value of f(n) is always lies on or below Cg(n).

The Notation Ω (BIG ‘Omega’)

O-Notation provides as asymptotic upper bound for a function; Ω-Notation provides as asymptotic upper bound for a function; Ω-Notation, provides an asymptotic lower-bound for a given function.

We say that the function  [read as “f of n is big “Omega” of g of n”], if and only if there exist two positive constants C and n0 such that

Fig. 2

Note that for all values of f(n) always lies on or above g(n).

The Notation θ (Theta)

Θ-Notation provides simultaneous both asymptotic lower bound and asymptotic upper bound for a given function.

Let f(n) and g(n) are two positive functions, each from the set of natural numbers (domain) to the positive real numbers. In some cases, we have  and  then .

We say that the function  [read as “f of n is Theta” of g of n”], if and only if there exist three positive constants C1, C2 and n0 such that

for all ...(i)

(Note that this inequality (1) represents two conditions to be satisfied simultaneously viz  and

clearly this implies if f(n) = O (g (n)) and f = Ω (g(n)) then f(n) = Θ (g(n)).

The following figure-1 shows the intuition behind the Θ-Notation.

Fig. 3

Note that for all values of n to the right of the n0 the value of f(n) lies at or above C1g(n) and at or below C2.g(n).

Hence inequality (1) simultaneously satisfied for C1 = 1,

C2 = 2 and .

Hence f(n) = Θ (g(n)).

Minimum Cost Spanning Trees (Prim’s Algorithm)

The algorithm is outlined below. It finds the set of edges T of a minimum cost spanning tree.

1. T  {}; X {1}; Y  V – {1}
2. while Y  {}
3. Let (x, y) be of minimum weight such that  and .
4.
5.
6.
7. end while