algorithms

Asymptotic Notations

Let’s start with the basic question, ‘What are Asymptotic Notations?’

Asymptotic notations are mathematical notations that describe the limiting behaviour of a function when the argument tends towards a particular value (or may be infinity). The phrase ‘limiting behaviour’ here is important. The notations describe the restriction and boundaries towards a function.

Let’s stay for a while in the math world and understand the three members that belong to this family.

Member 01: θ Notation
A function f(n) belongs to the set of θ(g(n)) if there exists positive constants C1 and C2 such that it can be packed between two functions C1g(n) and C2g(n), this being true from the value n0. The notation is graphically presented in the fig. 1 given below.

theta

Fig. 1: θ notation

For all n >= n0, the value of f(n) lies at or above C1g(n)  and at or below C2g(n). i.e,
C1 g(n) <= f(n) <= C2 g(n) for all n >= n0

Example:
As an example let us express the function f(n) = 10n + 10 using θ notation.
10n <= 10n+10 <= 15n
C1 = 10
C2 = 15
g(n) = n
n0 = 1

Member 02: O Notation
O notation is used to give an upper bound on a function, to within a constant factor. For all the values of n at and to the right of n0, the value of the function f(n) is on or below Cg(n).  The notation is graphically presented in the fig. 2 given below.

oh

Fig. 2: O notation

For all n >= n0, the value of f(n) lies at or below Cg(n) i.e,
f(n) <= C g(n) for all n >= n0

Example:
As an example let us express the function f(n) = 10n + 10 using O notation
10n+10 <= 15n
C = 15
g(n) = n
n0 = 1

Member 03: Ω Notation
Ω notation is used to give a lower bound on a function, to within a constant factor. For all the values of n at and to the right of n0, the value of the function f(n) is on or above Cg(n).  The notation is graphically presented in the fig. 3 given below.

omega

Fig. 3: Ω notation

For all n >= n0, the value of f(n) lies at or above Cg(n). i.e,
f(n) >= C g(n) for all n >= n0

Example:
As an example let us express the function f(n) = 10n + 10 using Ω notation.
10n+10 >= 10
C = 10
g(n) = n
n0 = 1

These notations that we understood from the math world can be used to characterize aspects or features of any domains applicable and relevant.

******

Asymptotic Notions for Algorithms
In algorithms we use asymptotic notations to characterize the running times of the algorithms. However, that said, they can be used to characterize some other or any other feature like space as well.

When we say running time, we need to be little more specific about the nature of the input – Is it the worst case, best case or an average case. Considering the cases and the notations, we can easily map the three notations to the three cases.

Hence we have the notations as:

Θ – Average Case

O – Worst Case

Ω – Best Case

 

 

 

Advertisements

Let me Know What you Think!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s