CS 201 Data Structures and Algorithms
Algorithm Analysis
Özyeğin University
School of Engineering
Emre Sefer
[Link]@[Link]
Slide materials partially adopted from Weiss, Goodrich & Tamassia
Introduction
◼ An algorithm’s execution time is related to the
number of operations it requires
◼ A concern for large problems (large input size) only
◼ Algorithm Analysis is independent of
◼ Specific implementations
◼ Computers
◼ Data
Özyeğin University CS 201 | Data Structures and Algorithms 2
Algorithm Analysis…
◼ Factors affecting the running time
◼ computer
◼ compiler
◼ algorithm used
◼ input to the algorithm
◼ the content
◼ the input size
◼ Note: We assume that instructions are
executed one after another
◼ no concurrent/parallel execution
Özyeğin University CS 201 | Data Structures and Algorithms 3
Analyzing running time
◼ We focus on the worst case
running time best case
average case
◼ Easier to analyze worst case
◼ Crucial to applications such as 120
games, finance and robotics 100
Running Time
80
◼ Two approaches 60
◼ Experimental
40
◼ Theoretical
20
0
1000 2000 3000 4000
Input Size
Özyeğin University CS 201 | Data Structures and Algorithms 4
Experimental Studies
9000
◼ Write a program
8000
implementing the
algorithm 7000
◼ Run the program with 6000
Time (ms)
inputs of varying size 5000
and composition 4000
◼ Use a method like 3000
clock() to get an 2000
accurate measure of 1000
the actual running time
0
◼ Plot the results 0 50 100
Input Size
Özyeğin University CS 201 | Data Structures and Algorithms 5
Limitations of Experiments
◼ It is necessary to implement the algorithm,
which may be difficult
◼ Results may not be indicative of the running
time on other inputs not included in the
experiment
◼ In order to compare two algorithms, the
same hardware and software environments
must be used
Özyeğin University CS 201 | Data Structures and Algorithms 6
Theoretical Analysis
◼ Can be applied on a high-level description of the
algorithm instead of an implementation, i.e., pseudocode
◼ Characterizes running time as
a function of the input size, n
◼ Takes into account all possible inputs
◼ Allows us to evaluate the speed of an algorithm
independent of the hardware/software environment
Özyeğin University CS 201 | Data Structures and Algorithms 7
Number of Operations
Özyeğin University CS 201 | Data Structures and Algorithms 8
Definitions
Özyeğin University CS 201 | Data Structures and Algorithms 9
Comparison
Özyeğin University CS 201 | Data Structures and Algorithms 10
Comparison
Özyeğin University CS 201 | Data Structures and Algorithms 11
Comparison
Özyeğin University CS 201 | Data Structures and Algorithms 12
Non-recursive Algorithms
Özyeğin University CS 201 | Data Structures and Algorithms 13
Non-recursive Algorithms
Özyeğin University CS 201 | Data Structures and Algorithms 14
Non-recursive Algorithms
Özyeğin University CS 201 | Data Structures and Algorithms 15
Non-recursive Algorithms
Özyeğin University CS 201 | Data Structures and Algorithms 16
Recursive Algorithms
Özyeğin University CS 201 | Data Structures and Algorithms 17
Recursive Algorithms
Özyeğin University CS 201 | Data Structures and Algorithms 18
Recursive Algorithms
Özyeğin University CS 201 | Data Structures and Algorithms 19
Master Theorem
Özyeğin University CS 201 | Data Structures and Algorithms 20
Master Theorem
Özyeğin University CS 201 | Data Structures and Algorithms 21
Master Theorem
Özyeğin University CS 201 | Data Structures and Algorithms 22
Master Theorem
Özyeğin University CS 201 | Data Structures and Algorithms 23
Sample Question
Özyeğin University CS 201 | Data Structures and Algorithms 24
Sample Question
Özyeğin University CS 201 | Data Structures and Algorithms 25
Sample Question
Özyeğin University CS 201 | Data Structures and Algorithms 26
Sample Question
Özyeğin University CS 201 | Data Structures and Algorithms 27
Math you need to review
◼ Summations
◼ Logarithms and Exponents
◼ 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
◼ Proof techniques ab /ac = a(b-c)
b = a logab
◼ Basic probability bc = a c*logab
Özyeğin University CS 201 | Data Structures and Algorithms 28