Analysis of Algorithms
undefined
A
n
a
l
y
s
i
s
o
f
a
l
g
o
r
i
t
h
m
s
W
h
a
t
a
r
e
w
e
g
o
i
n
g
t
o
l
e
a
r
n
?
Need to say that some algorithms are
“
better
” than others
Criteria for evaluation
Structure of programs (simplicity, elegance, etc)
Running time
Memory space
O
v
e
r
v
i
e
w
Running Time
Pseudo-code
Analysis of algorithms
Asymptotic notations
Asymptotic analysis
E
x
p
e
r
i
m
e
n
t
a
l
s
t
u
d
i
e
s
Run the program with various data sets
In a computer, and measure the wall clock time
In other words,
Write a program
implementing the algorithm
Run program
with inputs of varying size
Get an accurate measure
of running time and plot result
L
i
m
i
t
a
t
i
o
n
s
o
f
e
x
p
e
r
i
m
e
n
t
s
Perceived limitations of experiments include
To compare algA to algB, both algorithms
must be implemented
Ideally, algA and algB are to be compared
on the same hardware and under same software environments
Experiments can be done only
on a limited set of test inputs
=> it is critical that there is sufficient number
of representative test cases (hard problem)
A
l
g
o
r
i
t
h
m
s
,
a
n
d
i
n
p
u
t
s
Running time of algorithms
Typically depends on the input set, and its size (
n
)
We describe it using functions of
n
Algorithm
Input
Output
T
(
n
)
n
=
4
A
v
e
r
a
g
e
c
a
s
e
v
s
.
W
o
r
s
t
c
a
s
e
The average case behavior
is harder
to analyze since
You need to know a probability distribution of input
We focus on the worst case
running time
In certain apps (air traffic control,
weapon systems, etc)
Knowing the worst case time
is important
W
o
r
s
t
c
a
s
e
a
n
a
l
y
s
i
s
Some of the advantages include
Uses a high-level description (pseudo-code) of algorithm
Instead of an implementation
Characterizes running time as a function of input size n
Allows us to evaluate the speed of an algorithm
Independent of the hardware/software environment
G
e
n
e
r
a
l
m
e
t
h
o
d
o
l
o
g
y
Independent of
implementation hardware and software environments
Actual elapsed time depends on
Hardware, software (os), compiler
Use
high-level description
of the algorithm
instead of one of its implementations
Worry about order of magnitude
Count steps (don’t worry about of time each steps takes)
Ignore multiplicative constants
P
s
e
u
d
o
-
c
o
d
e
Pseudo-code is a description of an algorithm
For human eyes
only (mix of English and programming)
Brief and easy to read – and hopefully, understand !!
Example: finding the max element of an array
Algorithm
arrayMax
(
A
,
n
)
Input
array
A
of
n
integers
Output
maximum element of
A
currentMax
A
[0]
for
i
1
to
n
1
do
if
A
[
i
]
currentMax
then
currentMax
A
[
i
]
return
currentMax
P
s
e
u
d
o
c
o
d
e
D
e
t
a
i
l
s
Control flow
if
…
then
…
[
else
…]
while
…
do
…
repeat
…
until
…
for
…
do
…
Indentation replaces braces
Method declaration
Algorithm
method
(
arg
[,
arg
…])
Input
…
Output
…
Method call
var.method
(
arg
[,
arg
…])
Return value
return
expression
Expressions
Assignment
(like
in Java)
Equality testing
(like
in Java)
n
2
Superscripts and other
mathematical formatting
allowed
H
o
w
t
o
c
o
u
n
t
s
t
e
p
s
Comments, declarative statements (0)
Expressions and assignments (1)
Except for function calls
Cost for function needs to be counted separately
And then added to the cost for the calling statement
H
o
w
t
o
c
o
u
n
t
s
t
e
p
s
:
i
t
e
r
a
t
i
o
n
Iteration statements – for, while
Boolean expression + count
the number of times the body is executed
And then multiply by the cost of body
That is, the number of steps inside the loop
while <expression> do
<body of while>
H
o
w
t
o
c
o
u
n
t
s
t
e
p
s
:
s
w
i
t
c
h
o
r
i
f
e
l
s
e
Running time
of worst case statement + Boolean expression
Switch <
expression
>
case1: <
statement1
>
case2: <
statement2
>
….
C
o
u
n
t
i
n
g
P
r
i
m
i
t
i
v
e
O
p
e
r
a
t
i
o
n
s
By inspecting the pseudocode,
we determine the maximum number of primitive operations
executed by an algorithm, as a function of the input size
Algorithm
arrayMax
(
A
,
n
)
# operations
currentMax
A
[0]
2
for
i
1
to
n
1
do
2
n+
1
if
A
[
i
]
currentMax
then
2(
n
1)
currentMax
A
[
i
]
2(
n
1)
{ increment counter i
}
2(
n
1)
return
currentMax
1
Total
8
n
2
E
s
t
i
m
a
t
i
n
g
R
u
n
n
i
n
g
T
i
m
e
Algorithm
arrayMax
executes
8
n
2
primitive operations in the worst case.
Define:
a
= Time taken by the fastest primitive operation
b
= Time taken by the slowest primitive operation
Let
T
(
n
)
be worst-case running time of
arrayMax.
Then
a
(8
n
2)
T
(
n
)
b
(8
n
2)
Hence, the running time
T
(
n
)
is bounded
by two linear functions
G
r
o
w
t
h
R
a
t
e
o
f
R
u
n
n
i
n
g
T
i
m
e
Changing the hardware/ software environment
Affects
T
(
n
)
by a constant factor, but
Does not alter the growth rate of
T
(
n
)
The linear growth rate of the running time
T
(
n
)
is an intrinsic property of algorithm
arrayMax
B
i
g
-
O
h
N
o
t
a
t
i
o
n
Given functions
f
(
n
)
and
g
(
n
)
,
we say that
f
(
n
)
is
O
(
g
(
n
))
if there are positive constants
c
and
n
0
such that
f
(
n
)
cg
(
n
)
for
n
n
0
Example:
2
n
10
is
O
(
n
)
2
n
10
cn
(
c
2)
n
10
n
10
(
c
2)
Pick
c
3
and
n
0
10
B
i
g
-
O
h
E
x
a
m
p
l
e
Example: the function n
2
is not O(n)
n
2
cn
n
c
The above inequality cannot
be satisfied since
c
must be a
constant
C
o
n
s
t
a
n
t
f
a
c
t
o
r
s
The growth rate is not affected by
constant factors or
lower-order terms
Examples
1
0
2
n
+
1
0
5
i
s
a
l
i
n
e
a
r
function
1
0
5
n
2
+
1
0
8
n
i
s
a
quadratic function
S
e
v
e
n
i
m
p
o
r
t
a
n
t
f
u
n
c
t
i
o
n
s
Seven functions that often appear in algorithm analysis:
Constant
1
Logarithmic
log
n
Linear
n
N-Log-N
n
log
n
Quadratic
n
2
Cubic
n
3
Exponential
2
n
In a log-log chart,
the slope of the line
corresponds to the growth rate of the function
B
i
g
-
O
h
r
u
l
e
s
If f(n) is a
polynomial of degree d
,
then f(n) is
O(n
d
)
, i.e.
Drop lower-order terms
Drop constant factors
Use the
smallest possible class
of functions
Say “2n is O(n)” and never, ever say “2n is O(n
2
)”
Use the
simplest expression
of the class
Say “3n+5 is O(n)” instead of “3n+5 is O(3n)”
B
i
g
-
O
h
n
o
t
a
t
i
o
n
:
m
a
t
h
e
m
a
t
i
c
a
l
p
r
o
o
f
Given functions
f
(
n
)
and
g
(
n
)
,
we say that
f
(
n
)
is
O
(
g
(
n
))
if there are positive constants
c
and
n
0
such that
f
(
n
)
cg
(
n
)
for
n
n
0
Example:
2
n
10
is
O
(
n
)
2
n
10
cn
(
c
2)
n
10
n
10
(
c
2)
Pick
c
3
and
n
0
10
B
i
g
-
O
h
e
x
a
m
p
l
e
Example: the function n
2
is not O(n)
n
2
cn
n
c
The above inequality cannot be
satisfied since
c
must be a
constant
A
s
y
m
p
t
o
t
i
c
a
l
g
o
r
i
t
h
m
a
n
a
l
y
s
i
s
The asymptotic analysis
Determines the running time in
big-Oh notation
.
Two basic steps to perform the asymptotic analysis
Find the
worst-case number
of operations
as a function of the
input size
Then express this function with big-Oh notation
Example of arrayMax
E
x
a
m
p
l
e
o
f
a
n
a
l
y
s
i
s
Find that algorithm executes at most
8n-2 ops
Drop constant factors and lower order terms
Say that algorithm “
runs in O(n) time
”
Algorithm
arrayMax
(
A
,
n
)
Input
array
A
of
n
integers
Output
maximum element of
A
currentMax
A
[0]
for
i
1
to
n
1
do
if
A
[
i
]
currentMax
then
currentMax
A
[
i
]
return
currentMax
E
x
a
m
p
l
e
o
f
a
n
a
l
y
s
i
s
(
c
o
n
t
’
d
)
Find statement
Executed most of the time
In this case
Statement inside inner loop
Total number of time
Inner loop is executed
=> n(n-1)/2
Running time is O(n
2
)
I
n
t
u
i
t
i
o
n
b
e
h
i
n
d
a
s
y
m
p
t
o
t
i
c
n
o
t
a
t
i
o
n
M
a
t
h
y
o
u
n
e
e
d
t
o
r
e
v
i
e
w
(
C
h
a
p
t
e
r
3
)
Summations
Properties of logarithms and exponentials
p
r
o
p
e
r
t
i
e
s
o
f
l
o
g
a
r
i
t
h
m
s
:
log
b
(xy) = log
b
x + log
b
y
log
b
(x/y) = log
b
x - log
b
y
log
b
xa = alog
b
x
log
b
a = log
x
a/log
x
b
p
r
o
p
e
r
t
i
e
s
o
f
e
x
p
o
n
e
n
t
i
a
l
s
:
a
(b+c)
= a
b
a
c
a
bc
= (a
b
)
c
a
b
/a
c
= a
(b-c)
b = a
log
a
b
b
c
= a
c*log
a
b
Explore the world of algorithms through the lens of analysis. Learn the criteria for evaluating algorithms, understanding running time and memory space, and conducting experimental studies. Delve into limitations of experiments, algorithms and inputs, average case vs. worst case analysis, and the benefits of worst-case analysis.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
What are we going to learn? Need to say that some algorithms are better than others Criteria for evaluation Structure of programs (simplicity, elegance, etc) Running time Memory space
Overview Running Time Pseudo-code Analysis of algorithms Asymptotic notations Asymptotic analysis
Experimental studies Run the program with various data sets In a computer, and measure the wall clock time 9000 8000 In other words, Write a program implementing the algorithm 7000 6000 Time (ms) 5000 4000 Run program with inputs of varying size 3000 2000 1000 Get an accurate measure of running time and plot result 0 0 50 100 Input Size
Limitations of experiments Perceived limitations of experiments include To compare algA to algB, both algorithms must be implemented Ideally, algA and algB are to be compared on the same hardware and under same software environments Experiments can be done only on a limited set of test inputs => it is critical that there is sufficient number of representative test cases (hard problem)
Algorithms, and inputs n = 4 T(n) Input Algorithm Output Running time of algorithms Typically depends on the input set, and its size (n) We describe it using functions of n
Average case vs. Worst case The average case behavior is harder to analyze since You need to know a probability distribution of input best case average case worst case We focus on the worst case running time In certain apps (air traffic control, weapon systems, etc) 120 100 Running Time 80 60 40 Knowing the worst case time is important 20 0 1000 2000 Input Size 3000 4000
Worst case analysis Some of the advantages include Uses a high-level description (pseudo-code) of algorithm Instead of an implementation Characterizes running time as a function of input size n Allows us to evaluate the speed of an algorithm Independent of the hardware/software environment
General methodology Independent of implementation hardware and software environments Actual elapsed time depends on Hardware, software (os), compiler Use high-level description of the algorithm instead of one of its implementations Worry about order of magnitude Count steps (don t worry about of time each steps takes) Ignore multiplicative constants
Pseudo-code Pseudo-code is a description of an algorithm For human eyes only (mix of English and programming) Brief and easy to read and hopefully, understand !! Example: finding the max element of an array AlgorithmarrayMax(A, n) Input array A of n integers Output maximum element of A currentMax A[0] fori 1 ton 1 do ifA[i] currentMaxthen currentMax A[i] returncurrentMax
Pseudocode Details Method call var.method (arg [, arg ]) Control flow if then [else ] while do repeat until for do Indentation replaces braces Return value returnexpression Expressions Assignment (like = in Java) = Equality testing (like == in Java) n2 Superscripts and other mathematical formatting allowed Method declaration Algorithm method (arg [, arg ]) Input Output
How to count steps Comments, declarative statements (0) Expressions and assignments (1) Except for function calls Cost for function needs to be counted separately And then added to the cost for the calling statement
How to count steps: iteration Iteration statements for, while Boolean expression + count the number of times the body is executed And then multiply by the cost of body That is, the number of steps inside the loop while <expression> do <body of while>
How to count steps: switch or if else Running time of worst case statement + Boolean expression Switch <expression> case1: <statement1> case2: <statement2> .
Counting Primitive Operations By inspecting the pseudocode, we determine the maximum number of primitive operations executed by an algorithm, as a function of the input size AlgorithmarrayMax(A, n) currentMax A[0] fori 1 ton 1 do ifA[i] currentMaxthen currentMax A[i] { increment counter i } returncurrentMax # operations Total 2 2n+1 2(n 1) 2(n 1) 2(n 1) 1 8n 2
Estimating Running Time Algorithm arrayMax executes 8n 2 primitive operations in the worst case. Define: a = Time taken by the fastest primitive operation b = Time taken by the slowest primitive operation Let T(n) be worst-case running time of arrayMax.Then a (8n 2) T(n) b(8n 2) Hence, the running time T(n) is bounded by two linear functions
Growth Rate of Running Time Changing the hardware/ software environment Affects T(n) by a constant factor, but Does not alter the growth rate of T(n) The linear growth rate of the running time T(n) is an intrinsic property of algorithm arrayMax
Big-Oh Notation Given functions f(n) and g(n), we say that f(n) is O(g(n)) if there are positive constants c and n0 such that f(n) cg(n) for n n0 10,000 3n 2n+10 1,000 Example: 2n+10 is O(n) 2n+10 cn (c 2) n 10 n 10 (c 2) Pick c = 3 and n0 = 10 n 100 10 1 1 10 100 1,000 n
Big-Oh Example Example: the function n2 is not O(n) n2 cn 1,000,000 n^2 100n 10n n 100,000 n c 10,000 The above inequality cannot be satisfied since c must be a constant 1,000 100 10 1 1 10 100 1,000 n
Constant factors The growth rate is not affected by constant factors or 1E+26 Quadratic Quadratic Linear Linear 1E+24 1E+22 1E+20 lower-order terms 1E+18 1E+16 Examples 102n + 105 is a linear function 1E+14 T(n) 1E+12 1E+10 1E+8 1E+6 105n2+ 108n is a quadratic function 1E+4 1E+2 1E+0 1E+0 1E+2 1E+4 1E+6 1E+8 1E+10 n
Seven important functions Seven functions that often appear in algorithm analysis: Constant 1 Logarithmic log n Linear n N-Log-N n log n Quadratic n2 Cubic n3 Exponential 2n 1E+30 1E+28 Cubic 1E+26 Quadratic 1E+24 1E+22 Linear 1E+20 1E+18 1E+16 T(n) 1E+14 1E+12 1E+10 1E+8 1E+6 In a log-log chart, the slope of the line 1E+4 1E+2 1E+0 1E+0 1E+2 1E+4 1E+6 1E+8 1E+10 n corresponds to the growth rate of the function
Big-Oh rules If f(n) is a polynomial of degree d, then f(n) is O(nd), i.e. Drop lower-order terms Drop constant factors Use the smallest possible class of functions Say 2n is O(n) and never, ever say 2n is O(n2) Use the simplest expression of the class Say 3n+5 is O(n) instead of 3n+5 is O(3n)
Big-Oh notation: mathematical proof Given functions f(n) and g(n), we say that f(n) is O(g(n)) if there are positive constants c and n0 such that f(n) cg(n) for n n0 10,000 3n 2n+10 1,000 Example: 2n+10 is O(n) 2n+10 cn (c 2) n 10 n 10 (c 2) Pick c = 3 and n0 = 10 n 100 10 1 1 10 100 1,000 n
Big-Oh example Example: the function n2 is not O(n) n2 cn 1,000,000 n^2 100n 10n n 100,000 n c 10,000 The above inequality cannot be satisfied since c must be a constant 1,000 100 10 1 1 10 100 1,000 n
Asymptotic algorithm analysis The asymptotic analysis Determines the running time in big-Oh notation. Two basic steps to perform the asymptotic analysis Find the worst-case number of operations as a function of the input size Then express this function with big-Oh notation Example of arrayMax
Example of analysis Find that algorithm executes at most 8n-2 ops Drop constant factors and lower order terms Say that algorithm runs in O(n) time AlgorithmarrayMax(A, n) Input array A of n integers Output maximum element of A currentMax A[0] fori 1 ton 1 do ifA[i] currentMaxthen currentMax A[i] returncurrentMax
Example of analysis (contd) Find statement Executed most of the time In this case Statement inside inner loop Total number of time Inner loop is executed => n(n-1)/2 Running time is O(n2)
Intuition behind asymptotic notation
Math you need to review (Chapter 3) Summations Properties of logarithms and exponentials properties of logarithms: logb(xy) = logbx + logby logb (x/y) = logbx - logby logbxa = alogbx logba = logxa/logxb properties of exponentials: a(b+c) = aba c abc = (ab)c ab /ac = a(b-c) b = a logab bc = a c*logab
