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

- O(Big-”Oh”) Notation. [Maximum number of steps to solve a problem, (upper bound)]
- Ω (Big-”Omega”) Notation [Minimum number of steps to solve a problem, (lower bound)]
- θ (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 N_{0} such that

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

** **

**Fig. 1**

For all values of n to the right of n_{0}, 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 n_{0} 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 C_{1}, C_{2} and n_{0} 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 C_{1} = 1,

C_{2} = 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.

- T ← {}; X ← {1}; Y ← V – {1}
- while Y ≠ {}
- Let (x, y) be of minimum weight such that and .
- end while