Introduction to Algorithm Analysis

Lecture #1 of Algorithms, Data structures and Complexity

Joost-Pieter Katoen
Formal Methods and Tools Group
E-mail: katoen@[Link]

August 27, 2002

c JPK
#1: Introduction to Algorithm Analysis ADC (214020)

Overview
Introduction
– Measuring algorithm complexity: what, how and why?

Average, best and worst-case time complexity

– What are these concepts?

– Analyzing the linear search algorithm

Asymptotic growth rates

– The classes , and




– Practical relevance

Space complexity

Organisational matters

c JPK 1

#1: Introduction to Algorithm Analysis ADC (214020)

Algorithms and data structures

Algorithm = a recipe for solving a problem by a computer program

– examples: sorting, linear and binary search, matrix multiplication

It solves an algorithmic problem that is specified by describing:

– the set of instances it should work on (precondition)

– how the output should look like (postcondition)

Data structure = a way to store information

– e.g., trees, stacks, lists, queues etc. (implementations of Java collections)

Important issues: correctness, elegance, and efficiency

Efficient algorithms use effective data structures

c JPK 2

#1: Introduction to Algorithm Analysis ADC (214020)

Comparing the efficiency of algorithms

Important criteria:

– the amount of work done time complexity

– the amount of space used space complexity

time complexity space complexity complexity of algorithm





Assess efficiency of algorithms, independent of:

– type of computer used, programming language, programming skills, etc.

Technology improves things by a constant factor only

Even a supercomputer cannot rescue a “bad” algorithm

– a faster algorithm on a slower computer will always win

for sufficiently large inputs

c JPK 3

#1: Introduction to Algorithm Analysis ADC (214020)

Comparing the efficiency of algorithms

Analysis is based on choice of basic operations such as:

– “comparing two numbers” for sorting an array of numbers
– “multiplying two real numbers” for matrix multiplication

# basic operations should be good estimate of total # operations

# basic operations constitutes basis for determining the rate of growth

of the time complexity as the input gets larger

For input size typical running times (within a constant factor):
constant





logarithmic quadratic




linear exponential


c JPK 4

#1: Introduction to Algorithm Analysis ADC (214020)

Overview
Introduction

– Measuring algorithm complexity: what, how and why?

Average, best and worst-case time complexity

– What are these concepts?
– Analyzing the linear search algorithm

Asymptotic growth rates

– The classes , and




– Practical relevance

Space complexity

Organisational matters

c JPK 5

#1: Introduction to Algorithm Analysis ADC (214020)

Average, best and worst case complexity – Intuition

Consider a given algorithm

The worst case complexity of is the maximum # basic operations

performed by on any input of a certain size

The best case complexity of is the minimum # basic operations

performed by on any input of a certain size

The average case complexity of is the average # basic operations

performed by on any input of a certain size

Each of these complexities defines a function: time versus input size

c JPK 6

#1: Introduction to Algorithm Analysis ADC (214020)

Average, best and worst case complexity – Example






Run time










Input size

c JPK 7

#1: Introduction to Algorithm Analysis ADC (214020)

Average, best and worst case complexity – Formally

Let:

set of inputs of size



# basic operations needed for input






the probability that input occurs








The worst case complexity: max



 








The best case complexity:

min



 






The average case complexity:

 
















How do we know:
– by analyzing the algorithm under consideration




– by experience, or assumption (e.g., “all inputs occur equally frequent”)






c JPK 8

#1: Introduction to Algorithm Analysis ADC (214020)

Linear search
Input: array with entries and item to be looked up



Output: true if is in array and false otherwise

bool seqSearch int 

int int








int index ; // start at the front
bool found false; // assume absence of


while index found



found index ;
 




index index







return found



c JPK 9

#1: Introduction to Algorithm Analysis ADC (214020)

Analyzing linear search

Basic operation = comparison of integer with array element


is all permutations of elements out of a set of elements







, as in worst case is last element in array, or is not found






, as in best case is the first element in the array



, as on average half of the array needs to be checked?

 




– no, under reasonable assumptions (see next slide) we have:

in 
in


















– how to determine the function ?




we have to use a bit of probability theory and discrete maths



c JPK 10

#1: Introduction to Algorithm Analysis ADC (214020)

Average case complexity for linear search (I)

Distinguish between two scenarios:

– occurs in array ; this yields average complexity








– does not occur in array ; this yields average complexity








in  not in












 










not in in








, but how about ?











– assume all elements in the array are distinct, then:




in time



 


 

 
















c JPK 11

#1: Introduction to Algorithm Analysis ADC (214020)

Average case complexity for linear search (II)



in time




 


 


















(* if this takes comparisons *)



 





in




 















(* assume can equally well be at any index if it occurs in *)





















(* calculus *)














(* you all know this *)

















c JPK 12

#1: Introduction to Algorithm Analysis ADC (214020)

Average case complexity for linear search (III)

Putting the results together yields:

in in







 



















Note that if in equals




1, then 50% of checked

















0, then is entirely checked







, then 75% of checked









c JPK 13

#1: Introduction to Algorithm Analysis ADC (214020)

Optimality (I)

When is algorithm optimal? This depends on problem complexity:

– algorithm class: set of algorithms that use the same allowed operations
– measure of complexity: the basic operations to be considered

An algorithm is optimal if no algorithm in the same class exists that

performs fewer basic operations (“we cannot do better”)

– optimal = “the best possible”, but optimal “the best known”

Lower bound : for any algorithm in a class and any input size






there is some input of size that needs at least basic operations





Algorithm is optimal if 












c JPK 14

#1: Introduction to Algorithm Analysis ADC (214020)

Optimality (II)
Problem: find largest element in array of real (of size )


Class: comparisons of reals allowed, but no other manipulations
Measure of complexity: comparison of reals

real findMax real  int





real max






for index index index









if max index max index









return max



; is there any algorithm (in this class) that does fewer?











No! . So, this algorithm is optimal










c JPK 15

#1: Introduction to Algorithm Analysis ADC (214020)

Optimality (III)
Problem: compute the product of square matrices and


Class: , , and division of real numbers



Measure of complexity: multiplication of two reals

real matMult real int














for









for  















for








 

 

 
















return





; is there any algorithm (in this class) that does fewer?









is unknown!; best known algorithm requires mults










c JPK 16

#1: Introduction to Algorithm Analysis ADC (214020)

Overview
Introduction

– Measuring algorithm complexity: what, how and why?

Average, best and worst-case time complexity

– What are these concepts?

– Analyzing the linear search algorithm

Asymptotic growth rates

– The classes , and



– Practical relevance

Space complexity

Organisational matters

c JPK 17

#1: Introduction to Algorithm Analysis ADC (214020)

Asymptotic analysis

Exactly determining and is typically very hard, and













– use for comparison doubtful: is better than ?






– we want to ignore machine-dependent constants (e.g., processor speed)

Typically no exact analysis, but asymptotic analysis

– look at growth of execution time for


– thus ignoring small inputs and constant factors 
– intuition: drop lower order terms, e.g.,


 











(i.e., is the dominating factor when goes to )



– thus, we obtain lower/upper bounds on , and now!









– mathematical ingredient: asymptotic order of functions (classes , and )





c JPK 18

#1: Introduction to Algorithm Analysis ADC (214020)

Classes , and (I)


Let and be functions from (input size) to (run time)

 



is the set of functions that grow no faster than






– means is an upper bound on













is the set of functions that grow at least as fast as






– means is a lower bound on













is the set of functions that grow at the same rate as






– means is an upper bound on


 











and is a lower bound on






All assume some constant 

beyond which they are satisfied; small


values of are ignored



c JPK 19

#1: Introduction to Algorithm Analysis ADC (214020)

Classes , and (II)











Run time

Run time








Input size Input size











Run time







Input size


c JPK 20

#1: Introduction to Algorithm Analysis ADC (214020)

Classes , and (III)



Functions that grow
at least as fast as Functions that grow Functions that grow
no faster than


at the same rate as




c JPK 21

#1: Introduction to Algorithm Analysis ADC (214020)

The class big-oh

Formally, if such that





















Handy alternative: if for

















– note that if are differentiable then

























Example: consider . We have:









– since













– since for












– since for sufficiently large













Big-oh class gives an upper bound on complexity of a function

– tightest upper bounds are of most use! says more than










c JPK 22

#1: Introduction to Algorithm Analysis ADC (214020)

The class big-omega

Formally, if such that





















Handy alternative: if



















– recall that if are differentiable then

























Example: consider . We have:









– since













– since















– since for












Big-omega class gives a lower bound on complexity of a function

– tightest lower bounds are of most use! says more than









c JPK 23

#1: Introduction to Algorithm Analysis ADC (214020)

The class big-theta

if such that



























Handy alternative: if for some


















– recall if and only if and













Example: consider . We have:











– since













– since














– since but









Big-theta class gives a lower bound and upper bound on complexity

of a function

c JPK 24

#1: Introduction to Algorithm Analysis ADC (214020)

Some elementary properties

Reflexivity:

–





–





–





Transitivity:

– and imply











– and imply











– and imply











Symmetry:

– if and only if









Relation between and :

– if and only if









c JPK 25

#1: Introduction to Algorithm Analysis ADC (214020)

Actual run times – time complexity in practice

Compl.













Solution time


10 .00033 sec .0015 sec .0013 sec .0034 sec .001 sec
10 .003 sec .03 sec .13 sec 3.4 sec 4 yr




10 .033 sec .45 sec 13 sec .94 hour


10 .33 sec 6.1 sec 22 min 39 days



10 3.3 sec 1.3 min 1.5 days 108 yr



Note: impact of high constant factors diminishes if grows

c JPK 26

#1: Introduction to Algorithm Analysis ADC (214020)

Maximum solvable input size

Compl.













time allowed Maximum solvable input size

1 sec 30,000 2,000 280 67 20

1 min 1,800,000 82,000 2,200 260 26

We cannot handle input 60 times larger if we increase time (or speed) by factor 60

c JPK 27

#1: Introduction to Algorithm Analysis ADC (214020)

On the effect of faster computers

Let be the maximum input size that can be handled in a fixed time


What happens to if we take a computer that is times faster?



# steps performed maximum feasible input size
on input of size




































c JPK 28

#1: Introduction to Algorithm Analysis ADC (214020)

Overview
Introduction

– Measuring algorithm complexity: what, how and why?

Average, best and worst-case time complexity

– What are these concepts?

– Analyzing the linear search algorithm

Asymptotic growth rates

– The classes , and




– Practical relevance

Space complexity

Organisational matters

c JPK 29

#1: Introduction to Algorithm Analysis ADC (214020)

Space complexity

besides run-time, the amount of memory used is important!

Suppose we want to sing a song that lasts time units (length )


– since can be large we memorize songs which require a small amount of brain
– let be the space complexity of songs of length



What bounds can we establish on ?



– 
since in the worst case we must memorize each word







– since we have to know something about the song to sing it









Can we do better if we structure the song using refrains?

[”The Complexity of Songs” by Donald Knuth, 1984]

c JPK 30

#1: Introduction to Algorithm Analysis ADC (214020)

The refrain

Repeat a refrain after each verse in the song:

Soo.. Bye, bye miss American Pie

Drove me Chevy to the levee but the levee was dry
Them good old boys were drinking whiskey and rye?
Singing this will be the day that I die
this will be the day that I die [Don McLean]

Memorize a refrain only once, but sing it times. Does this help?






No. Not in terms of asymptotic complexity

– If # repetitions (verse-size + refrain-size)

– then # repetitions verse-size + refrain-size



– If refrain-size = verse-size, is halved, but still in








c JPK 31

#1: Introduction to Algorithm Analysis ADC (214020)

The days of Xmas

Reduce by structuring the song differently; verse is, e.g.:





On the th day of Xmas, my true love gave to me gift












On the first day of Xmas, my true love gave to me a bottle of wine

But the time to sing it is (ignoring refrains):















If then , thus






c JPK 32

#1: Introduction to Algorithm Analysis ADC (214020)

100 bottles of beer

Boring songs for really long car trips:

bottles of beer on the wall, bottles of beer

You take one down and pass it around
bottles of beer on the ball

[Andy Kaufman]

Remember: template of , plus the value of (taking bits)












– thus
 






Can we obtain the lower bound? Yes, by eliminating the need to

count
That’s the way, uh-huh, uh-huh
I like it, uh-huh, huh
[KC & the Sunshine band, 1977]

c JPK 33

#1: Introduction to Algorithm Analysis ADC (214020)

Overview
Introduction

– Measuring algorithm complexity: what, how and why?

Average, best and worst-case time complexity

– What are these concepts?

– Analyzing the linear search algorithm

Asymptotic growth rates

– The classes , and




– Practical relevance

Space complexity

Organisational matters

c JPK 34

#1: Introduction to Algorithm Analysis ADC (214020)

Course topics
Algorithm analysis techniques Priority queues

Elementary data structures Graph algorithms

Sorting Dynamic programming

Red-black trees Computability

Hashing Complexity classes and


+ Algorithm design strategies
– Divide-and-conquer, dynamic programming, greedy methods
– Breadth-first and depth-first searching

c JPK 35

#1: Introduction to Algorithm Analysis ADC (214020)

Course material

Computer Algorithms – Introduction to Design & Analysis

by Sara Baase and Allen van Gelder

publisher Addison-Wesley, third edition, 2000

Possibly extended with handouts

Online course information on Teletop

– the slides of the lectures

– homework
– other relevant information (e.g., rules)

c JPK 36

#1: Introduction to Algorithm Analysis ADC (214020)

Course work

Werkcolleges: weekly; after 3 weeks every other week

4 Programming assignments: from week 4 on, every other week

– presence is mandatory
– mandatory to be allowed to do the exam!

Homework: two series of (optional) homework

– results can only positively influence your mark

– handed in/out at: see schedule on web

Exam: open book exam on November 26 (2002)

You only get acquainted with the material by actively solving exercises yourself

c JPK 37