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
