## Asymptotic Notations

Asymptotic notations are mathematical tools to

represent the time complexity of algorithms for

asymptotic analysis.

The main idea of asymptotic analysis is to have a

measure of the efficiency of algorithms that don’t

depend on machine-specific constants and doesn’t

require algorithms to be implemented and time taken

by programs to be compared.

The following asymptotic notations are mostly used to

represent the time complexity of algorithms.

O − Big Oh

Ω − Big omega

θ − Big theta

o − Little Oh

ω − Little omega

1) ‘O’ (Big Oh)

‘O’ (Big Oh) is the most commonly used notation.

A function f(n) can be represented is the order of

g(n) that is O(g(n)), if there exists a value of

positive integer n as n0 and a positive constant c

such that –

f(n)⩽c.g(n)

for n>n0 in all case

Hence, function g(n) is an upper bound for

function f(n), as g(n) grows faster than f(n).

Example-

Let us consider a given function,

f(n)=4.n 3 +10.n 2 +5.n+1

Considering g(n)=n 3 , f(n)⩽5.g(n)

for all the values of n>2

Hence, the complexity of f(n) can be represented

as O(g(n)) , i.e. O(n 3 )

2) Ω: Asymptotic Lower Bound

We say that f(n)=Ω(g(n))

when there exists constant c that f(n)⩾c.g(n)for

all sufficiently large value of n. Here n is a positive

integer. It means function g is a lower bound for

function f; after a certain value of n, f will never

go below g.

Example-

Let us consider a given function,

f(n)=4.n 3 +10.n 2 +5.n+1.

Considering g(n)=n 3

, f(n)⩾4.g(n) for all the values of n>0.

Hence, the complexity of f(n) can be represented

as Ω(g(n)) , i.e. Ω(n 3 )

3) θ: Asymptotic Tight Bound

We say that f(n)=θ(g(n)) when there exist

constants c1 and c2 that c1.g(n)⩽f(n)⩽c2.g(n)for

all sufficiently large value of n. Here n is a positive

integer.

This means function g is a tight bound for function

f.

Example-

Let us consider a given function,

f(n)=4.n 3 +10.n 2 +5. n +1

Considering g(n)=n 3

4.g(n)⩽f(n)⩽5.g(n)for all the large values of n.

Hence, the complexity of f(n) can be represented

as θ(g(n)) i.e. θ(n 3 ).

4) O – Notation

The asymptotic upper bound provided by O-

notation may or may not be asymptotically tight.

The bound 2.n 2 =O(n 2 ) is asymptotically tight, but

the bound 2.n=O(n 2 )is not.

We use o-notation to denote an upper bound that

is not asymptotically tight. We formally define

o(g(n)) (little-oh of g of n) as the set f(n) = o(g(n))

for any positive constant c>0 and there exists a

value n0>0, such that 0⩽f(n)⩽c.g(n).

Intuitively, in the o-notation, the function f(n)

becomes insignificant relative to g(n) as n

approaches infinity; that is,

limn→∞(f(n)g(n))=0

Example-

Let us consider the same function,

f(n)=4.n 3 +10.n 2 +5.n+1

Considering g(n)=n 4

limn→∞ ( (4.n 3 +10.n 2 +5.n+1) / n 4 )=0

Hence, the complexity of f(n) can be

represented as o(g(n)) , i.e. o(n 4 ).

5) ω – Notation

We use ω-notation to denote a lower bound that

is not asymptotically tight. Formally, however, we

define ω(g(n)) (little-omega of g of n) as the set

f(n) = ω(g(n)) for any positive constant C > 0 and

there exists a value n0>0 , such that

0⩽c.g(n)<f(n).

For example, n 22 =ω(n),

but n 22 ≠ω(n 2 ). The relation f(n)=ω(g(n))implies that

the following limit exists

limn→∞(f(n)g(n))=∞

That is, f(n) becomes arbitrarily large relative to

g(n) as n approaches infinity.

Example-

Let us consider same function,

f(n)=4.n 3 +10.n 2 +5.n+1

Considering g(n)=n 2

limn→∞(4.n 3 +10.n 2 +5.n+1n 2 )=∞

Hence, the complexity of f(n) can be represented

as o(g(n)) , i.e. ω(n2).

**Recent Job Posts**

- Engineering Jobs (BE/Btech/ME/Mtech)
- Motherson (MSSL) Off Campus Drive 2021
- Experienced Jobs (Jobs for experienced professionals)
- Nielsen Off Campus Drive 2021 | Trainee Analyst
- Management Jobs (MBA/BBA etc jobs)
- Jobs for BA/MA and other graduates
- Prepare for CAT Exam 2021
- Anagha Engineers Digital_Marketing internship
- Mechanical Engineering Internship 2021
- HackerRank Off Campus Drive 2021
- Stellar Infosys Web_Development Internship

#### [ **Important** ]

*All Company names, logos, and brands are the Intellectual Property of their respective owners. All company, product, and service names used on this website are for identification purposes only.**We are not associated with any company/agency/agent whose jobs are*posted on*mechomotive.com, We are just an information provider for job openings. Read our Disclaimer Policy and Term of Service for more information*

For more job offers, CLICK HERE