Design and Analysis of Algorithms
Lecture 2: Analysis of Algorithms & some Preliminaries
BSCS-BSAI-BSSE
Dr. Muhammad Ilyas Fakhir
Computer Science Department
GC University Lahore
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 1 / 34
Outlines
1 Analysis Techniques
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 2 / 34
A high-level view of analysis of algorithms
Figure: A high-level view of analysis of algorithms
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 3 / 34
Analyzing an algorithm
Analyzing an algorithm
Analyzing an algorithm determines the amount of “time” that algorithm takes
to execute.
1 This is not really a number of seconds or
2 any other clock measurement but
3 rather an approximation of the number of operations that an algorithm
performs.
4 The number of operations is related to the execution time,
5 so we will sometimes use the word time to describe an algorithm’s
computational complexity.
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 4 / 34
Contd..
Contd..
The actual number of seconds it takes an algorithm to execute on a
computer is not useful in our analysis because
we are concerned with the relative efficiency of algorithms that solve a
particular problem.
the actual execution time is not a good measure of algorithm efficiency
because
an algorithm does not get “better” just because we move it to a faster
computer or
“worse” because we move it to a slower one.
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 5 / 34
Number of Operations
Number of Operations
The actual number of operations done for some specific size of input data
set is not very interesting nor does it tell us very much.
Instead, our analysis will determine an equation that relates the number
of operations that a particular algorithm does to the size of the input.
We can then compare two algorithms by comparing the rate at which
their equations grow.
The growth rate is critical because there are instances where algorithm A
may take fewer operations than algorithm B when the input size is small,
but many more when the input size gets large.
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 6 / 34
Analyzing an algorithm
Analyzing an algorithm
Analyzing an algorithm has come to mean predicting the resources that the
algorithm requires.
Generally, by analyzing several candidate algorithms for a problem, we can
identify a most efficient one.
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 7 / 34
Algorithms span a vast space
Algorithms span a vast space
The definition
Finite Set of Instructions to accomplish a task
spans a very vast space. We will only discuss a few kinds of algorithms.
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 8 / 34
Efficiency Measures
Efficiency Measures
Performance of a solution
Most of the software problems do not have a single best solution
Then how do we judge these solutions?
The solutions are chosen based on performance measures
Performance Measures
Time
Quality
Simplicity
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 9 / 34
Measuring the Running Time
Measuring the Running Time
How should we measure the running time of an algorithm?
Experimental Study
Write a program that implements the algorithm
Run the program with data sets of varying size and composition.
Use a method like System.currentTimeMillis() to get an accurate measure of
the actual running time.
The resulting data set should look something like:
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 10 / 34
Beyond Experimental Studies
Beyond Experimental Studies
Experimental studies have several limitations:
It is necessary to implement and test the algorithm in order to determine
its running time.
Experiments can be done only on a limited set of inputs, and 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 should be used.
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 11 / 34
General Methodology
General Methodology
We will now develop a general methodology for analyzing the running
time of algorithms that
Uses a high-level description of the algorithm instead of testing one of its
implementations.
Takes into account all possible inputs.
Allows one to evaluate the efficiency of any algorithm in a way that is
independent from the hardware and software environment.
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 12 / 34
Analysis of Algorithms
Analysis of Algorithms
Refers to predicting the resources required by the algorithm, based on
size of the problem
The primary resources required are T IME AND S PACE
Analysis based on time taken to execute the algorithm is called Time
complexity of the Algorithm
Analysis based on the memory required to execute the algorithm is called
Space complexity of the Algorithm
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 13 / 34
Contd..
Importance of Analysis of Algorithm
When a programmer builds an algorithm during design phase of software life
cycle, he/she might not be able to implement it immediately. This is because
programming comes in later part of the software life cycle. But there is a need
to analyze the algorithm at that stage. This will help in forecasting how much
time the algorithm takes or how much primary memory it might occupy when
it is implemented. So analysis of algorithm becomes very important.
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 14 / 34
Complexity of an algorithm
Complexity of an algorithm
Complexity of an algorithm represents the amount of resources required while
executing the algorithm.
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 15 / 34
tradeoff between the time and space complexity
tradeoff between the time and space complexity
There will always be a tradeoff between the time and space complexity.
Most of the problems which require more space will take less time to
execute and vice versa.
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 16 / 34
Space Complexity
Space Complexity
The space needed by a program has the following components:
Instruction space
Data space
Environment stack space
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 17 / 34
Contd..
Space Complexity
Instruction space: Space needed to store the object code.
Data space: Space needed to store constants & variables.
Environment stack space: Space needed when functions are called. If
the function, function A calls another function function B then the
return address and all the local variables and formal parameters are to
stored.
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 18 / 34
Input Size
Input Size
For a given problem, we characterize the input size, n, appropriately:
Sorting – The number of items to be sorted
Graphs – The number of vertices and/or edges
Numerical – The number of bits needed to represent a number
The choice of an input size greatly depends on the elementary operation; the
most relevant or important operation of an algorithm.
Comparisons
Additions
Multiplications
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 19 / 34
Orders of Growth
Orders of Growth
Small input sizes can usually be computed instantaneously, thus we are
most interested in how an algorithm performs as
n→∞
Indeed, for small values of n, most such functions will be very similar in
running time. Only for sufficiently large n do differences in running time
become apparent.
As
n→∞
the differences become more and more stark (clear).
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 20 / 34
Mathematical Analysis of Algorithms
Mathematical Analysis of Algorithms
After developing pseudo-code for an algorithm, we wish to analyze its
efficiency as a function of the size of the input, n in terms of how many times
the elementary operation is performed. Here is a general strategy:
1 Decide on a parameter(s) for the input, n.
2 Identify the basic operation.
3 Evaluate if the elementary operation depends only on n (otherwise
evaluate best, worst, and average-case separately.
4 Set up a summation corresponding to the number of elementary
operations
5 Simplify the equation to get as simple of a function f(n) as possible.
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 21 / 34
Analysis Examples
Example I
A LGORITHM (U NIQUE E LEMENTS )
Consider the following code.
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 22 / 34
Analysis Example
Example I - Analysis
What Required for this Algorithm?
For this algorithm, what is
The elementary operation?
Input Size?
Does the elementary operation depend only on n?
The outer for-loop is run (n − 2)times; more formally, it contributes
Σn−1
i=1
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 23 / 34
Analysis Example
Example I - Analysis
Inner For-Loop
The inner for-loop depends on the outer for-loop, so it contributes
Σnj=i+1
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 24 / 34
Analysis based on the nature of the problem
Analysis based on the nature of the problem
The analysis of the algorithm can be performed based on the nature of the
problem.
Thus we have:
Worst case analysis
Average case analysis
Best case analysis
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 25 / 34
Worst Case
Worst Case:
Under what condition/s does the algorithm when executed consumes
maximum amount of resources.
It is the maximum amount of resource the algorithm can consume for
any value of problem size.
Worst case is an important analysis because it gives us an idea of the
most time an algorithm will ever take.
Worst-case analysis requires that we identify the input values that cause
an algorithm to do the most work.
For searching algorithms, the worst case is one where the value is in the
last place we check or is not in the list.
This could involve comparing the key to each list value for a total of N
comparisons.
The worst case gives us an upper bound on how slowly parts of our
programs may work based on our algorithm choices.
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 26 / 34
Best Case
Best Case
Under what condition/s does the algorithm when executed consumes
minimum amount of resources.
As its name indicates, the best case for an algorithm is the input that
requires the algorithm to take the shortest time.
This input is the combination of values that causes the algorithm to do the
least amount of work.
If we are looking at a searching algorithm, the best case would be if the
value we are searching for (commonly called the target or key) was the
value stored in the first location that the search algorithm would check.
This would then require only one comparison no matter how complex the
algorithm is.
Notice
For searching through a list of values, no matter how large, the best case will
result in a constant time of 1. Because the best case for an algorithm will usually
be a very small and frequently constant value, we will not do a best-case
analysis very frequently.
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 27 / 34
Average Case
Average Case
This is between worst case & best case.
It is probabilistic in nature.
Average-case running times are calculated by first arriving at an
understanding of the average nature of the input, and then performing a
running-time analysis of the algorithm for this configuration.
Average case analysis is done by considering every possibility are
equally likely (occurring probability of events is same) to happen
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 28 / 34
Contd..
Average Case: Contd..
Average-case analysis is the toughest to do because there are a lot of
details involved.
The basic process begins by determining the number of different groups
into which all possible input sets can be divided.
The second step is to determine the probability that the input will come
from each of these groups.
The third step is to determine how long the algorithm will run for each of
these groups.
All of the input in each group should take the same amount of time, and
if they do not, the group must be split into two separate groups.
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 29 / 34
What is Analysis?
What is Analysis?
The analysis of an algorithm provides background information that gives
us a general idea of how long an algorithm will take for a given problem
set.
For each algorithm considered, we will come up with an estimate of how
long it will take to solve a problem that has a set of N input values.
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 30 / 34
Input Classes
Input Classes
Input plays an important role in analyzing algorithms because it is the input
that determines what the path of execution through an algorithm will be.
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 31 / 34
Goals for Design an Algorithm
Goals for Design an Algorithm
Before we start with our discussion of algorithms we should think about our
goals when designing algorithms.
1 Algorithms have to be correct.
2 Algorithms should be as efficient as possible.
3 Algorithms should be simple.
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 32 / 34
Contd..
Contd..
The first goal in this list is so self-evident that it is often overlooked.
The importance of the last goal might not be as obvious as the other
goals.
However, the reasons for the last goal are economical:
If it takes too long to code an algorithm, the cost of the implementation
might well be unaffordable.
Furthermore, even if the budget is unlimited there is another reasons to
conflict for simple algorithms:
If the conceptual complexity of an algorithm is too high, it may become
impossible to check the correctness of the implementation.
Therefore, the third goal is strongly related to the first goal.
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 33 / 34
References I
Introduction to Algorithms, T. H. Cormen, C. E. Leiserson, and R. L. Rivest, MIT Press, McGraw-Hill, 3rd Edition, New York, NY,
2010.
Slides from Infosys Technologies Ltd 2004
Analysis of Algorithms: An Active Learning Approach; Jeffrey J. McConnell Jones and Bartlett Publishers International Barb House,
Barb Mews London, UK 2001
Alfred V. Aho, John E. Hopcraft, and Jeffrey D. Ullman: Data Structures and Algorithms, Addison-Wesley, 1987
Robert Sedgewick : Algorithms in Java, fourth edition, Pearson, 2011
This book has a nice booksite containing a wealth of additional material. This book seems to be the best choice for the working
practitioner. Furthermore, Professor Sedgewick teaches a course on algorithms on coursera that is based on this book.
Furthermore, there is a set of video lectures from Professor Roughgarden at coursera.
Algorithms, written by Sanjoy Dasgupta, Christos H. Papadimitriou, and Unmesh V. Vazirani is a short text book on Algorithms that
is available online.
Data Structures and Algorithms written by Kurt Mehlhorn and Peter Sanders
Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms 34 / 34
