Algorithm
Lecture 09
1
Algorithms
DEF: An algorithm is a finite set of precise
instructions for performing a computation or solving
a problem.
Synonyms for a algorithm are: program, recipe,
procedure, and many others.
2
Pseudo-Java
• Possible alternative to text’s pseudo-Java
Start with “real” Java and simplify:
int f(int[] a){
int x = a[0];
for(int i=1; i<a.length; i++){
if(x > a[i])
x = a[i];
}
return x;
}
3
Pseudo-Java Version 1
integer f(integer_array (a1, a2, …, an) ){
x = a1
for(i =2 to n){
if(x > ai)
x = ai
}
return x
}
4
Pseudo-Java version 2
INPUT: integer_array V = (a1, a2, …, an)
begin
x = a1
for(y V)
if(x > y)
x = y
end
OUTPUT: x
5
Algorithm for Surjectivity
boolean isOnto( function f: n m ){
if( m > n ) return false // can’t be onto
soFarIsOnto = true
for( j = 1 to m ){
soFarIsOnto = false;
for(i = 1 to n ){
if ( f(i ) == j )
soFarIsOnto = true;
if( !soFarIsOnto ) return false;
}
}
return true;
}
6
Improved Algorithm for Surjectivity
boolean isOntoB( function f: (1, 2,…, n) (1, 2,…, m) ){
if( m > n ) return false // can’t be onto
for( j = 1 to m )
beenHit[ j ] = false; // make it false
for(i = 1 to n )
beenHit[ f(i ) ] = true; // assigned on are true
for(j = 1 to m )
if( !beenHit[ j ] )
return false;
return true;
}
7
Algorithmic Complexity
Compare the running time of 2 previous algorithms for
testing surjectivity.
Measure running time by counting the number of
“basic operations”.
8
Running Time
Basic steps—
Assignment Increment
Comparison Negation
Return Random array access
Function output access etc.
In a particular problem, may tell you to consider other
operations (e.g. multiplication) and ignore all others
9
Running time of 1st algorithm
boolean isOnto( function f: (1, 2,…, n) (1, 2,…, m)
){
if( m > n ) return false 1+1 step OR:
soFarIsOnto = true 1 step (assigment)
for( j = 1 to m ){ m loops: 1 increment plus
soFarIsOnto = false 1 step (assignment)
for(i = 1 to n ){ n loops: 1 increment plus
if ( f(i ) == j ) 1 step possibly leads to:
soFarIsOnto = true 1 step (assignment)
if( !soFarIsOnto ) 1 step possibly leads to:
return false 1 step (return)
}
}
return true; possibly 1 step
}
WORST-CASE
Running time of 1st algorithm
running time:
Number of steps = 1
OR
1+
1 step (m>n) OR: m·
1 step (assigment) (1+ 1 +
m loops: 1 increment plus n·
1 step (assignment) (1
n loops: 1 increment plus +1
1 step possibly leads to: +1
1 step (assignment) +1
+1
1 step possibly leads to:
)
1 step (return)
)
possibly 1 step
1+m(2+5n)+1 +1
= 2+2m+5mn
=5mn+2m+2
= 1 (if m>n) OR
5mn+2m+2
Running time of 2nd algorithm
boolean isOntoB( function f: (1, 2,…, n) (1, 2,…, m) ){
if( m > n ) return false 1 step OR:
for( j = 1 to m ) m loops: 1 increment plus
beenHit[ j ] = false 1 step (assignment)
for(i = 1 to n )
n loops: 1 increment plus
beenHit[ f(i ) ] = true
1 step (assignment)
for(j = 1 to m )
if( !beenHit[ j ] ) m loops: 1 increment plus
return false 1 step possibly leads to:
return true 1 step
} possibly 1 step
.
Running time of 2nd algorithm
WORST-CASE running time:
1 step (m>n) OR: Number of steps = 1 OR 1+
m loops: 1 increment plus m · (1+
1 step (assignment) 1)
n loops: 1 increment plus + n · (1+
1 step (assignment) 1)
m loops: 1 increment plus + m · (1+ 1+2m+2n+3m+1
1 step possibly leads to: 1 = 2+5m+2n
=5m+2n+2
1 step + 1)
possibly 1 step + 1
. = 1 (if m>n) OR 5m + 2n + 2
Comparing Running Times
1. At most 5mn+2m+2 for first algorithm
2. At most 5m+2n+2 for second algorithm
Worst case when m n so replace m by n:
5n 2+2n+2 vs. 7n+2
To tell which is better, look at dominant term:
5n2+2n+2 vs. 7n+2
So second algorithm is better.
14
Comparing Running Times: Issues
1. 5n 2+2n+2 , 7n+2 are more than just their biggest
term. Consider n = 1.
2. Number of “basic steps” doesn’t give accurate
running time.
3. Actual running time depends on platform.
4. Overestimated number of steps: under some
conditions, portions of code will not be seen.
15
Running Times Issues Big-O Response
1. Asymptotic notation (Big-O) gives partial resolution to
problems:
2. Different lengths of basic steps, just change 5n2 to
Cn 2 for some constant, so doesn’t change largest
term
16
Running Times Issues Big-O Response
1. Asymptotic notation (Big-O) gives partial resolution to
problems:
2. Basic operations on different (but well-designed)
platforms will differ by a constant factor. Again,
changes 5n2 to Cn2 for some constant.
17
Notational Issues
Big-O notation is a way of comparing functions. Notation
unconventional:
EG: 3x3 + 5x2 – 9 = O (x3)
Doesn’t mean
“3x 3 + 5x 2 – 9 equals the function O(x3)”
Which actually means
“3x3+5x2 –9 is dominated by x3”
Read as: “3x 3+5x 2 –9 is big-Oh of x3”
18
Intuitive Notion of Big-O
Asymptotic notation captures behavior of functions for
large values of x.
EG: Dominant term of 3x3+5x2 –9 is x3.
As x becomes larger and larger, other terms
become insignificant and only x3 remains in the
picture:
19
Intuitive Notion of Big-O domain
y = 3x 3+5x 2 –9
y=x3
y=x2
y=x
Intuitive Notion of Big-O domain
y = 3x 3+5x 2 –9
y=x3
y=x2
y=x
Intuitive Notion of Big-O domain
y = 3x 3+5x 2 –9
y=x3
y=x2
y=x
Intuitive Notion of Big-O domain
y = 3x 3+5x 2 –9
y=x3
y=x2
y=x
23
Intuitive Notion of Big-O
In fact, 3x 3+5x 2 –9 is smaller than 5x 3 for large enough
values of x:
y = 5x 3
y = 3x 3+5x 2 –9
y=x2
y=x
24
Big-O. Formal Definition
f (x ) is asymptotically dominated by g (x ) if there’s a
constant multiple of g (x ) bigger than f (x ) as x
goes to infinity:
DEF: Let f , g be functions with domain R0 or N and
codomain R. If there are constants C and k such
x > k, |f (x )| C |g (x )|
then we write:
f (x ) = O ( g (x ) )
f does not grow faster than g
25
Big-O. Example
EG: Show that 3x 3 + 5x 2 – 9 = O (x 3).
Previous graphs show C = 5 good guess.
Find k so that
3x 3 + 5x 2 – 9 5x 3
for x > k
26
EG: Show that 3x 3 + 5x 2 – 9 = O (x 3).
Find k so that
3x 3 + 5x 2 – 9 5x 3
for x > k
1. Collect terms: 5x 2 ≤ 2x 3 + 9
27
EG: Show that 3x 3 + 5x 2 – 9 = O (x 3).
Find k so that
3x 3 + 5x 2 – 9 5x 3
for x > k
1. Collect terms: 5x 2 ≤ 2x 3 + 9
2. What k will make 5x 2 ≤ x 3 for x > k ?
28
EG: Show that 3x 3 + 5x 2 – 9 = O (x 3).
Find k so that
3x 3 + 5x 2 – 9 5x 3
for x > k
1. Collect terms: 5x 2 ≤ 2x 3 + 9
2. What k will make 5x 2 ≤ x 3 for x > k ?
3. k = 5 !!
29
EG: Show that 3x 3 + 5x 2 – 9 = O (x 3).
Find k so that
3x 3 + 5x 2 – 9 5x 3
for x > k
1. Collect terms: 5x 2 ≤ 2x 3 + 9
2. What k will make 5x 2 ≤ x 3 for x > k ?
3. k = 5 !!
4. So for x > 5, 5x 2 ≤ x 3 ≤ 2x 3 + 9
30
EG: Show that 3x 3 + 5x 2 – 9 = O (x 3).
Find k so that
3x 3 + 5x 2 – 9 5x 3
for x > k
1. Collect terms: 5x 2 ≤ 2x 3 + 9
2. What k will make 5x 2 ≤ x 3 for x > k ?
3. k = 5 !
4. So for x > 5, 5x 2 ≤ x 3 ≤ 2x 3 + 9
5. Solution: C = 5, k = 5
31
Show that f ( x) x 2 x 1 is O( x )
2 2
If x>1 then
x<x2 and
1<x2
C=4 and k=1
If x>2 then
2x<=x2 and
1<= x2
C=3 and k=2
2 3
Show that 7 x is O( x )
If x>7 then
7x2 < x3 and
C=1 and k=7
If x>1 then
7x2 < 7x3 and
C=7 and k=1
Big-O and limits
LEMMA: If the limit as x of the quotient |f (x) / g (x)|
exists then f (x ) = O ( g (x ) ).
EG: 3x 3 + 5x 2 – 9 = O (x 3 ). Compute:
3x 3 5 x 2 9 3 5 / x 9 / x3
lim 3
lim 3
x x x 1
…so big-O relationship proved.
34
Big-O. Negative Example
x 4 O (3x 3 + 5x 2 – 9) :
No pair C, k exist for which
x > k implies C (3x 3 + 5x 2 – 9) x 4
Argue using limits: 4
x x
lim lim
x C (3 x 5 x 9)
3 2 x C (3 5 / x 9 / x 3 )
x 1
lim lim x
x C (3 0 0) 3C x
x 4 always catches up regardless of C. •
35
Intermission
36
Show that f ( x) x 2 x 1 is O( x )
2 2
If x>1 then
x<x2 and
1<x2
C=4 and k=1
If x>2 then
2x<=x2 and
1<= x2
C=3 and k=2
2 3
Show that 7 x is O( x )
If x>7 then
7x2 < x3 and
C=1 and k=7
If x>1 then
7x2 < 7x3 and
C=7 and k=1
Big-O and limits
LEMMA: If the limit as x of the quotient |f (x) / g (x)|
exists then f (x ) = O ( g (x ) ).
EG: 3x 3 + 5x 2 – 9 = O (x 3 ). Compute:
3x 3 5 x 2 9 3 5 / x 9 / x3
lim 3
lim 3
x x x 1
…so big-O relationship proved.
39
Big-O. Negative Example
x 4 O (3x 3 + 5x 2 – 9) :
No pair C, k exist for which
x > k implies C (3x 3 + 5x 2 – 9) x 4
Argue using limits: 4
x x
lim lim
x C (3 x 5 x 9)
3 2 x C (3 5 / x 9 / x 3 )
x 1
lim lim x
x C (3 0 0) 3C x
x 4 always catches up regardless of C. •
40
Review algorithm
Count the number of steps in the following code segment
i := 1
t := 0
while i ≤ n
t := t + i
i := i+1
41
Review Algorithm
Find Big O notation for the following code segment
for i = 1 to n
j=n;
while j >= 1
j=j-1;
42
Review Algorithm
Find Big O notation for the following code segment
for i = 1 to n{
j:=n;
while j >= 1{
j:=j-1;
}
}
43
Review Algorithm
Find Big O notation for the following code segment
do_it_now(n){
r ← 0;
for i ← 1 to n {
for j ← 1 to i {
for k ← j to i+j {
r ← r+1;
}
}
}
return r;
}
44
Review Algorithm
Give a steps count and give a big-O estimate of the
algorithm. (hint: n =x.length)
int do_it(int [] x)
{
int i,j;
int count =0;
for(i=0;i<x.length;++i){
for(j=0;j<i;++j){
if(x[i] + x[j]<0)
count+=1;
}
}
return count;
}
45
Review Algorithm
Calculate the number of steps for this function. (consider:
length(A) = m)
do_it(A:array){
for j=2 to length(A){
key=A[j]
i=j-1
while i>0 and A[i]>key {
A[i+1]=A[i]
i--
}
A[i+1]:=key
}
}
46
Review Algorithm
Give as good a big-O estimate as possible for each of
these functions.
1.(2n 1)(1 log n 3 )
2.4n 6n 2 log n
( n 2 1)(n 2 3)(n 2 5)
3.
n( n 2 2)(n 2 4)
4.3n 2 2n log( n 2 1)
47
Review Algorithm
Give as good a big-O estimate as possible for each of
these functions.
1.(2n 1)(1 log n 3 )
2.4n 6n 2 log n
( n 2 1)(n 2 3)(n 2 5)
3.
n( n 2 2)(n 2 4)
4.3n 2 2n log( n 2 1)
48
Review Algorithm
Give as good a big-O estimate as possible for each of
these functions.
1. n 3 n 8 O(max(n 3 , n,1)) O (n 3 )
2. log n n O (max(log n, n)) O ( n)
3. n log n O((n)(log n)) O( n log n)
n!
4. O ((n!)(1)) O(n!)
7
O (n) O (n log n) O (n 3 ) O (n!)
49
Thank You
50
