Asymptotic Notations

Design & Analysis of Algorithms
Asymptotic notations
D Bheekya
1
Asymptotic efficiency
• Asymptotic efficiency means study of algorithms efficiency for large inputs.

• To compare two algorithms with running times f(n) and g(n), we need a rough measure
that characterizes how fast each function grows as n grows.
• Hint: use rate of growth
• Compare functions asymptotically!
• (i.e., for large values of n)
Functions ordered by growth rate
Function Name
1 Growth is constant
logn Growth is logarithmic
n Growth is linear
nlogn Growth is n-log-n
n2 Growth is quadratic
n3 Growth is cubic
2n Growth is exponential
n! Growth is factorial
functions growth order: 1 < logn < n < nlogn < n2 < n3 < 2n < n!
To get a feel for how the various functions grow with n, you are advised to study the
following figure:
● The low order terms and constants in a function are relatively insignificant for large n
○ n2 + 100n + log10n + 1000 ~ n2
i.e., we say that n2 + 100n + log10n + 1000 and n2 have the same rate of growth
● Some more examples

○ n4 + 100n2 + 10n + 50 is ~ n4
○ 10n3 + 2n2 is ~ n3
○ n3 - n2 is ~ n3
○ constants
■ 10 is ~ 1
■ 1273 is ~ 1
Asymptotic/order Notations
• Asymptotic/order notation describes the behavior of functions for the large inputs.
• Asymptotic notations are mathematical tools to represent the time and space
complexity of algorithms
• Asymptotic notations are used to make meaningful statements about time and
space complexity.
• Asymptotic notations don’t depend on machine-specific constants and don’t
require algorithms to be implemented.
• Types of Asymptotic Notations:
– Big Oh(O) notation
– Omega (Ω) notation
– Theta (Θ) notation
Big Oh(O) notation
The Big Oh(O) notation describes a nearest or tighter upper bound on the asymptotic growth
rate of the function f.
Definition: [Big “oh’’] : the function f(n) = O(g(n)) (read as “f of n is big oh of g of n”) if and only
if there exist positive constants c and n0 such that f(n) ≤ cg(n) for all n, n ≥ n0.
• The definition states that the function f(n) is at
most c times the function g(n) except when n is
smaller than n0.
• In other words, f(n) grows slower than or same
rate as” g(n).
• When providing an upper –bound function g for f,
we normally use a single term in n.
Big Oh(O) notation
– Examples
• f(n) = 3n+2
● 3n + 2 <= 4n, for all n >= 2, ∴3n + 2 = Ο (n)
• f(n) = 10n2+4n+2
● 10n2+4n+2 <= 11n2, for all n >= 5, ∴ 10n2+4n+2 = Ο (n2)
• f(n)=6*2n+n2=O(2n)
● 6*2n+n2 ≤7*2n for n≥4 , ∴ 6*2n+n2=O(2n)
Big Oh(O) notation
• It is also possible to write 10n2+4n+2 = O(n3) since 10n2+4n+2 <=7n3 for n>=2
• Although n3 is an upper bound for 10n2+4n+2, it is not a tight upper bound; we can find
a smaller function (n2) that satisfies big oh relation.
• But, we can not write 10n2+4n+2 =O(n), since it does not satisfy the big oh relation for
sufficiently large input.
Omega (Ω) notation
The omega notation describes a nearest or tight lower bound on the asymptotic growth rate
of the function f.
Definition: f(n) = Ω(g(n)) (read as “f of n is omega of g of n”) iff there exist positive constants
c and n0 such that f(n) ≥ cg(n) for all n, n ≥ n0.
• The definition states that the function f(n) is at

least c times the function g(n) except when n is
smaller than n0.
• In other words,f(n) grows faster than or same
rate as” g(n).
Omega (Ω) notation
– Examples
• f(n) = 3n+2
● 3n + 2 >= 3n, for all n >= 1, ∴3n + 2 = Ω (n)
• f(n) = 10n2+4n+2
● 10n2+4n+2 >= n2, for all n >= 1, ∴ 10n2+4n+2 = Ω (n2)
• It also possible to write 10n2+4n+2 = Ω(n) since 10n2+4n+2 >=n for n>=0
• Although n is a lower bound for 10n2+4n+2, it is not a tight lower bound; we can find a
larger function (n2) that satisfies omega relation.
• But, we can not write 10n2+4n+2 = Ω(n3), since it does not satisfy the omega relation for
sufficiently large input.
Theta (Θ) notation
The Theta notation defines exact asymptotic behaviour. It describes both upper bound and
lower bound (a tight bound) on the asymptotic growth rate of the function f.
Definition: f(n) = Θ(g(n)) (read as “f of n is theta of g of n”) iff there exist positive constants
c1, c2, and n0 such that c1g(n) ≤ f(n) ≤ c2g(n) for all n, n ≥ n0.
• The definition states that the function f(n) lies

between c1 times the function g(n) and c2
times the function g(n) except when n is
smaller than n0.
• In other words, f(n) grows same rate as” g(n).
Theta (Θ) notation
• Examples:-
– f(n) = 3n+2
• 3n <= 3n + 2 <= 4n, for all n >= 2, ∴ 3n + 2 = Θ (n)
– f(n) = 10n2+4n+2
• n2<= 10n2+4n+2 <= 11n2, for all n >= 5, ∴ 10n2+4n+2 = Θ (n2)
• But, we can not write either 10n2+4n+2= Θ(n) or 10n2+4n+2= Θ(n3), since neither of these
will satisfy the theta relation.
Big-Oh, Theta, Omega
Tips :
• Think of O(g(n)) as “less than or equal to” g(n)
– Upper bound: “grows slower than or same rate as” g(n)
• Think of Ω(g(n)) as “greater than or equal to” g(n)

– Lower bound: “grows faster than or same rate as” g(n)
• Think of Θ(g(n)) as “equal to” g(n)

– “Tight” bound: same growth rate
• (True for large N)

Little ο notation:
● Little o notation is used to describe an upper bound that cannot be tight. In

other words, loose upper bound of f(n).
● Little o is a rough estimate of the maximum order of growth whereas Big-Ο
may be the actual order of growth.
16
Little ο notation:
The function f(n) = o(g(n)) (read as f of n is little oh of g of n") iff
For example-1:- If f(n) = n2 and g(n) = n3 then check whether f(n) = o(g(n)) or not.
17
18
Example: Towers of Hanoi problem
Algorithm TowersOfHanoi(n, A, B, C)
{
If (n ≥ 1) then
{
TowersOfHanoi(n-1, A, C, B);
Write(“move top disk from tower” , A, “to
top of tower”, B);
TowersOfHanoi(n-1, C, B, A);
}
}
Time complexity of Towers of Hanoi
• T(n) = T(n-1) + 1 + T(n-1) = 2T(n-1) + 1
= 2 * ( 2 * T(n-2) + 1) + 1
= (2 ^ 2) * T(n-2) + 2^1 + 2^0
:
= (2^k) * T(n-k) + 2^(k-1) + 2^(k-2) + ... + 2^0
Base condition T(0) = 1
n – k = 0 => n = k;
put, k = n
T(n)=2^n T(0)+2^(n-1)+....+2^1+2^0
It is GP series, and sum is 2^(n+1)-1
T(n) = O(2^n) which is exponential.
21

Asymptotic Notations

Uploaded by

Copyright:

Available Formats

Asymptotic Notations

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Asymptotic Notations

Uploaded by

Copyright:

Available Formats

Design & Analysis of Algorithms

• Asymptotic efficiency means study of algorithms efficiency for large inputs.

● Some more examples

• The definition states that the function f(n) is at

• The definition states that the function f(n) lies

• Think of Ω(g(n)) as “greater than or equal to” g(n)

• Think of Θ(g(n)) as “equal to” g(n)

• (True for large N)

● Little o notation is used to describe an upper bound that cannot be tight. In

The function f(n) = o(g(n)) (read as f of n is little oh of g of n") iff

You might also like