ANALYZING ALGORITHMS
FARIHA TABASSUM ISLAM
Asymptotic Notation
Analyzing Runtime
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 2
ASYMPTOTIC NOTATIONS
for sufficiently large input (), f is always less than
for sufficiently large input (), f is always greater than
: exact bound of f(n). What does it mean?
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 3
ASYMPTOTIC NOTATIONS
Assume: ,
is
is
is
is
is
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 4
ASYMPTOTIC ANALYSIS
If the max value of is then is cheaper than
However if , is cheaper
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 5
ASYMPTOTIC ANALYSIS
If the max value of is then is The term asymptotic means
approaching a value (e.g. infinity) or
cheaper than
curve arbitrarily closely (i.e., as some
However if , is cheaper sort of limit is taken).
[Asymptotic]
Therefore, asymptotically,
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 6
ASYMPTOTIC ANALYSIS
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 7
EXACT COST ANALYSIS
BEST AND WORST CASE ANALYSIS
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 8
EXACT COST ANALYSIS: EXAMPLE 1
Consider Line 3. How many times
the line 3 executes?
Best case: 0
Worst case:
Average case:
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 9
EXACT COST ANALYSIS: EXAMPLE 1
The running time of this algorithm
therefore belongs to both and . which
means it is in
Line 1:
Line 2:
Line 3
Best case: 0
Worst case:
Average case:
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 10
EXACT COST ANALYSIS: EXAMPLE 2
Line Worst Best
What is the time complexity of the 5
code? Derive the best and worst case
run-time and express in notation. Asym
ptotic
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 11
EXACT COST ANALYSIS: EXAMPLE 2
Line Worst Best
3 0
Asym
ptotic
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 12
EXACT COST ANALYSIS: EXAMPLE 2
Observe Line 1
value of : , … until less than 0
therefore, runs times
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 13
EXACT COST ANALYSIS: EXAMPLE 2
Observe Line 4
value of :
value of :
Therefore, inner statements of loop in
line 4 runs times
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 14
EXACT COST ANALYSIS: EXAMPLE 2
Best case:
Worst case: or
The running time of this algorithm therefore belongs to both and
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 15
for (i=1; i<=n;i++)
for (i=n;i>=1;i--)
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 16
EXACT COST ANALYSIS: EXAMPLE 3
Line Worst Best
1
log 4 𝑛=log 2 𝑛= ∗ log 2 𝑛
2 1
2
2
Derive the running-time equations and 5
express in "O" notation
Asym
ptotic
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 17
EXACT COST ANALYSIS: EXAMPLE 3
Line Worst Best
1
log 4 𝑛=log 2 𝑛= ∗ log 2 𝑛
2 1 n/3+1
2
2 n/3
3 0
Asym
ptotic
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 18
EXACT COST ANALYSIS: EXAMPLE 3
Observe Line 4
value of :
Therefore, inner statements of loop in
line 4 runs times
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 19
EXACT COST ANALYSIS: EXAMPLE 3
Best case:
Worst case: or
The running time of this algorithm therefore belongs to both and
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 20
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 21
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 22
EXACT COST ANALYSIS: EXAMPLE 4
Line Worst Best
Asym
ptotic
Derive the running-time equations and
express in "O" notation
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 23
EXACT COST ANALYSIS: EXAMPLE 4
Line Worst Best
Asym
ptotic
Derive the running-time equations and
express in "O" notation
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 24
How many times line 1 run?
if n=2 then
0, 1, 2, 3 (when , it fails to execute
statements inside the loop)
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 25
#times Line 2 runs
// checks and fails. Inner statements does
not run.
// checks and fails. Inner statements does
not run.
// Inner statements run once
// Inner statements run twice
// Inner statements run thrice
Total
cost =
=
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 26
#times line 3 runs
// does not run.
// does not run.
// runs once
// runs twice
// runs thrice
Total
cost of =
Line 3 =
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 27
Best case:
Worst case:
Therefore, this is
The running time of this algorithm therefore belongs to both and , which means it is in
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 28
EXACT COST ANALYSIS: EXAMPLE 5
Line Worst Best
Derive the running-time equations and 5
express in "O" notation
Asym
ptotic
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 29
EXACT COST ANALYSIS: EXAMPLE 5
Line Worst Best
Derive the running-time equations and 5
express in "O" notation
Asym
ptotic
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 30
EXACT COST ANALYSIS: EXAMPLE 5
#times Line 2 runs
// checks and fails. Inner statements does
not run.
// checks and fails. Inner statements does
not run.
// Inner statements run once
// Inner statements run twice
// Inner statements run thrice
Total
cost =
=
=
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 31
EXACT COST ANALYSIS: EXAMPLE 5
#times Line 3 runs
// does not run.
// does not run.
Total
cost =
=
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 32
EXACT COST ANALYSIS: EXAMPLE 6
Line Worst Best
Derive the running-time equations and
express in "O" notation
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 33
Asym
PRACTICE
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 34
QUESTION PATTERNS
Derive the best and worst case running-time equations and express in O
notation.
Derive the exact cost equation and express in O notation
Provide best and worst case examples
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 35
QUICK EVALUATION 1
Which picture shows the asymptotic tight bound?
Show that is
Show that is not
Show that is
Show that is
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 36
QUICK EVALUATION 2
What is the time complexity of the
code?
Derive the exact cost equation and
express in O notation
https://www.geeksforgeeks.org/practice-questions-time-com
plexity-analysis/
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 37
QUICK EVALUATION 2
What is the time complexity of the
code?
Derive the exact cost equation and
express in O notation
https://www.geeksforgeeks.org/practice-questions-time-com
plexity-analysis/
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 38
QUICK EVALUATION 3
What is the time complexity of the
code?
Derive the exact cost equation and
express in O notation
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 39
QUICK EVALUATION 3
What is the time complexity of the
code?
Derive the exact cost equation and
express in O notation
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 40
QUICK EVALUATION 4
What is the time complexity of the
code?
Derive the exact cost equation and
express in O notation
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 41
RESOURCES
https://www.cs.auckland.ac.nz/courses/compsci220s1t/lectures/lecturenotes/GG-l
ectures/BigOhexamples.pdf
http://www.cs.utsa.edu/~bylander/cs3233/big-oh.pdf
https://youtu.be/FEnwM-iDb2g
https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-
faster-than-processing-an-unsorted-array/11227902#11227902
FARIHA TABASSUM ISLAM, LECTURER, DEPT. OF CSE, UIU 42
