02 CS316_algorithms_Asymptotic_Notations(2).pdf

CS316: ALGORI
THM S
Lecture 2
ANALYSI
SOFALGORI
THM S
1
Prepared by: Assoc. Prof. Ensaf Hussein
Presented by:
Assoc. Prof. Wessam El-Behaidy
Dr. Mohammed El-Said

ASYMPTOTIC NOTATIONSAND BASIC
EFFICIENCYCLASSES

3
BOUNDS(ASYMPTOTIC NOTATIONS)
Critical factor for problem size n:
 I
S NOT the exact number of basic operations
executed for given n
 I
S how number of basic operations grow s as n
increases
Consequently:
 Focus on how performance grows as n  

 Ignore constant factors
Call this:Asymptotic Order of Grow th

Bounds describe the limiting behavior of algorithm
complexity at large (n). They are:
Worst Case:Upper Bound (Big O complexity)
Best Case:Lower Bound (Big  complexity)
Exact (Big  complexity)
Approach:classify functions (i.e. of algorithms
performance) based on their growth rates and divide
into sets
4
BOUNDS (ASYMPTOTI
C NOTATI
ONS)
W
Q
O

O-NOTATION: DEFINITION
Worst Case Upper Bound (Big O)
class of functions (algorithms) f(n) that grow
no faster than g(n)
order of growth of f(n) ≤ order of growth of
g(n) (within constant multiple).
f(n) of the algorithm
g(n) is one of growth functions

O-NOTATION :
x 
O (x2)? Yes, c = 1, n0=1 works fine.
10x  O (x)? Yes, c = 11, n0=1 works fine.
x2  O (x)? No, no matter what c and n0
we pick, cx2 > x for big enough x
f (n) 
O (g (n)) means:there are positive
constants c and n0 such that f(n)  c g(n) for all
values n  n0.
Then:

O-NOTATION :
O(n3)
O(n2)
f(n) = n2.5
f(n) = 12n2 + n
f(n) = n3.1 – n2
Hence,only the fastest-grow ing term in f matters

O-NOTATI
ON :EXAMPLES
Example : Using basic definition, we show that
3n2 + 10n ϵ O(n2)
Consider, 10 ≤ n for n ≥ 10 ( obvious !
)
10n ≤ n2 for n ≥ 10 ( Multiplying both sides with n )
3n2+10n ≤ 3n2 + n2 for n ≥ 10 ( Adding 3n2 to both sides )
=4n2 (Simplifying )
3n2 + 10 n ≤ c.n2 for n ≥ n0 where c =4 and n0= 10 (Solution)
Therefore, it follows from the basic definition that
3n2 +10n = O(n2)
The choice of constant c is not unique. However, for each
different c there is a corresponding value of n0 which satisfies
the basic relation .This behavior is illustrated by the next
example

Example : In the preceding example it was shown that
3n2 + 10n ≤ c.n2 for c=4, n0=10.
We now show that the relation holds true for a different value of
c and corresponding n0.
Consider n ≤ n2 for n ≥ 1 ( Obvious)
10n ≤ 10n2 for n≥ 1 (Multiplying both sides with 10 )
3n2 +10 n ≤ 3n2 + 10n2 for n≥ 1 ( Adding 3n2 on both
sides)
3n2 +10n ≤ 13n2 for n ≥ 1 ( Simplifying )
Or,
3n2 +10n ≤ c.n2, for n ≥ n0 where c=13, n0=1 ( Solution )
Therefore, by basic definition,
3n2 + 10n = O(n2)

O-NOTATION EXAMPLE
COMPARISON OF GROWTH RATES
The results of analysis in the preceding examples
are plotted in the next diagram.
It can be seen that the function cg(n) =4n2 ( c= 4)
overshoots the function f(n)= 3n2 + 10n for n0=10.
Also, the function cg(n) =13n2 ( c =13 ) grows
faster than f(n) = 3n2 + 10n for n0=1

Growth of functions 13n2 and 4n2 versus the function 3n2 + 10 n
Tight upper
bound

Ω-NOTATION: DEFINITION
Best Case:Low er Bound (Big  
class of functions f(n) that grow at least as
fast as g(n)
If order of growth of f(n) ≥ order of growth
of g(n) (within constant multiple).
f(n) ≥ c.g(n) for all n ≥ n0

Ω-NOTATION: DEFINITION
Let f and g be functions from the set of integers or
the set of real numbers to the set of real numbers. We
say that f(x) is  (g(x)) or f(x) =  (g(x))
(read as: “
f(x) is big-omega of g(x)”
) if there are
constants C and n0 such that
c.g(n) ≤ f(n) for all n ≥ n0
lim
→ ∞
( )
( )
= c ,
where c is a positive constant such that 0 < c ≤ ∞

Ω-NOTATION
BASIC METHOD
Example: Using basic definition, we show that
n3 ϵ Ω(n2).
For, n3 ≥ n2 for n ≥ 0
i.e. we can select c=1 and n0= 0

02 CS316_algorithms_Asymptotic_Notations(2).pdf

Θ-NOTATION: DEFINITION
Exact (Big  complexity)
Class of functions f(n) that grow at same rate
as g(n)
Order of growth of f(n) = order of growth
of g(n) (within constant multiples).
c2.g(n) ≤ f(n) ≤ c1.g(n)
for all n ≥ n0

Θ-NOTATION: DEFINITION
Let f and g be functions from the set of integers or the set
of real numbers to the set of real numbers. We say that
f(x) = (g(x)) or f(x) is in order (g(x))
if f(x) = O(g(x)) and f(x) =  (g(x)).
such that for some positive constants c1 , c2 and positive
integer n0 ,
0 < c2.g(n) ≤ f(n) ≤ c1.g(n) for all n ≥ n0
lim
→ ∞
( )
( )
= c ,
where c is a positive constant such that 0 < c < ∞

Example: We show that ½ n (n-1) ϵ θ(n2).
We need to prove that
c2 g(n) ≤ F(n) ≤ c1 g(n) for all n ≥ no
first, consider the upper bound,
F(n) ≤ c1 g(n)
½ n2 – ½ n ≤ ½ n2 for all n ≥ 0.
Second, consider the lower bound,
F(n) ≥ c2 g(n)
½ n2 – ½ n ≥ ½ n2 – ½ n ½ n for all n ≥ 2.
= ¼ n2.
Hence we can select c2 = ¼ , c1= ½ , and n0 = 2.
½ n(n-1) = ½ n2 – ½ n

21
BOUNDS(ASYMPTOTIC NOTATIONS)
W
Q
O
f(n) ≤ c × g(n)
for all n ≥ n0
n
n0
c × g(n)
f(n)
f(n) є O(g(n))
f(n) ≥ c × g(n)
for all n ≥ n0
n0
f(n)
c × g(n)
n
f(n) є Ω(g(n))
c2×g(n) ≤ f(n) ≤ c1×g(n)
for all n ≥ n0
n
f(n) є Θ(g(n))
c1 × g(n)
c2 × g(n)
f(n)
n0

Theorem :
(
1) Suppose f1(
x
)= O(
g1(
x
)
)and f2(
x
)= O(
g2(
x
)
)then
(
f1+f2)
(
x
) = O (
max
(
g1(
x
)
,g2(
x
)
)
Example 1:Theorem 1
If our problem contains sorting inputs, then search within.
Consider sorting algorithm= O(n2) comparisons and then binary
search = O(log2n) comparisons, then:
efficiency is O(max{n2, log2n}) = O(n2)

Example 2:Theorem 1
Consider the summation f(n) consisting of basic functions :
f(n) = n +√n + n1.5+ lg n + n lg n + n2
We have seen that
lg n < √n < n <n lg n <n1.5 < n2
which means that the function n2 grows faster than all other
functions in the expression
Thus,
f(n) = n + √n + n1.5+ lg n + n lg n + n2
= O( max (n , √n , n1.5, lg n , n lg n , n2 ) )
= O(n2)

Theorem :
(
2)Suppose f1(
x
)= O(
g1(
x
)
)and f2(
x
)= O(
g2(
x
)
)then
(
f1f2)
(
x
) = O (
g1(
x
)
.g2(
x
)
)
Example :Theorem 2
If we have two nested loops,
inner loop = O(n) and outer loop = O(n), so:
The efficiency is O(n . n) = O(n2)

Theorem :Polynomial
(
3)Let ( ) = ∑ =
= a0 + a1x+ a2x
2+ …+ anx
n , where
ai are real numbers, Then F(
x
)= O(
x
n)
Example :Theorem 3
The polynomial
is order of x5 (or O(x5)).
The polynomial
is order of x199 (or O(x199) )

Theorem :Transitivity
(
4)If f(
x
)= O(
g (
x
)
)and h(
x
)˃ g(
x
)for sufficiently large x
0, it
follows that f (
x
)= O(
h (
x
)
)
Example : Theorem 4
x2+2x+1 = O(x2); and x3 > x2
 x2+2x+1 = O(x3)

Theorem :
(
1) Suppose f1(
x
)= O(
g1(
x
)
)and f2(
x
)= O(
g2(
x
)
)then
(
f1+f2)
(
x
) = O (
max
(
g1(
x
)
,g2(
x
)
)
(
2)Suppose f1(
x
)= O(
g1(
x
)
)and f2(
x
)= O(
g2(
x
)
)then
(
f1f2)
(
x
) = O (
g1(
x
)
.g2(
x
)
)
(
3)Let ( ) = ∑ =
= a0 + a1x+ a2x
2+ …+ anx
n , where
ai are real numbers, Then F(
x
)= O(
x
n).
(
4)If f(
x
)= O(
g (
x
)
)and h(
x
)˃ g(
x
)for sufficiently large x
0, it
follows that f (
x
)= O(
h (
x
)
)

28
NOTE:
• All logarithmic functions loga n belong to the
same class order of (log n) no matter what the
logarithm’
s base a > 1 is
• Exponential functions an have different orders of
growth for different a’
s
• order log n < order n
>0) < order an <
order n!< order nn

QUESTI
ON…
Cost Function: tA(n) = n2 + 200n + 10000
• Which term in the function is most important
(dominates)?
It depends on the size of n
• n = 20, tA(n) = 400 + 4000 + 10000
• The constant, is the dominating term
• n = 100, tA(n) = 10000 + 20000 + 10000
• 200n is the dominating term
• n = 1000, tA(n) = 1000000 + 200000 + 10000
• n2 is the dominant term
29

REFERENCES
Anany Levitin, Introduction to the design and analysis of
algorithms, 2nd Edition.
Chapter 1, sections 1.1, 1.2
Chapter 2, Sections 2.1,2.2
Kenneth H. Rosen, Discrete Mathematics and its applications,
7th Edition .
Chapter 3 Algorithms

02 CS316_algorithms_Asymptotic_Notations(2).pdf

Recommended

More Related Content

Similar to 02 CS316_algorithms_Asymptotic_Notations(2).pdf (20)

Recently uploaded (20)

02 CS316_algorithms_Asymptotic_Notations(2).pdf