Design and Analysis of

Algorithm

Tanveer Ahmed Siddiqui

Department of Computer Science

COMSATS University, Islamabad
 Recap

Lecture No 1-4

Department of Computer Science 2

 Design and
Analysis of an
Algorithm

Department of Computer Science

 Two main issues related to
algorithms
 How we design an algorithms?
 Selection of appropriate designing technique.
 What sequence of steps one typically goes through?
 The description of algorithm at an abstract level
by means of a pseudo language
 Why we analyze an algorithm?
 To estimate how long a program will run.
 To estimate the largest input that can
reasonably be given to the program.
 To compare the efficiency of different
algorithms.
 To help focus on the parts of code that are
executed the largest number of times.
 To
Department choose
of Computer Sciencean algorithm for an application.
 Algorithm Design and Analysis
Process

Understand the problem

Decide on : algorithm
design techniques etc.

Design an algorithm

Department of Computer Science

 Understand the problem

Decide
Decideonon:algorithm
algorithm
design techniques etc.

Design an algorithm

Prove correctness

Department of Computer Science

 Understand the problem

Decide on : algorithm
design techniques etc.

Design an algorithm

Prove correctness

Analyze efficiency etc.

Department of Computer Science

 Understand the problem

Decide on : algorithm
design techniques etc.

Design an algorithm

Prove correctness

Analyze efficiency etc

efficiency
Code the algorithm
Department of Computer Science
 Analysis of Algorithm

Lecture No 5

Fundamentals of the Analysis of

Algorithm Efficiency

(Analysis Framework.)

Department of Computer Science

 Reading
Material

Read Chapter 2
Fundamentals of the Analysis
of Algorithm Efficiency

Department of Computer Science

 Today
Covered
After completing this lecture, you will be
able to understand:
What does analysis of Algorithm mean?
Why we analyze an algorithm?
How to analyze an algorithm
 Experimental Studies/Naïve Approach
 Theoretical/ Mathematical Analysis
 Explain how to choose the operations that
are counted and why others are not

Department of Computer Science

 MOTIVATIO
N
Why performance
analysis?

Department of Computer Science

 Why is it important?
 There are many algorithms that can solve
a given problem.
 Suppose we are given two algorithms for
a task; how do we find out which one is
better?
 Computer programmers are often
concerned with two questions:
 How much time does an algorithm need to
complete?
 How much memory does an algorithm need
for its computation?

Department of Computer Science 13

 Why is it important?
 Suppose there is a list of n numbers, and
we want to arrange them in ascending
order. We design following two algorithms
for solving this problem

 Which algorithm is best? Sort_A or Sort_B

Department of Computer Science
 Why is it important?
 Suppose you are participating in a
programming contests: The size of the input
data is given in the problem statement.
Suppose you found an algorithm.
 How to answer the following question
before writing the actual code?
 Is your algorithm worth implementing?
 Will it solve the largest test cases in time?
 If you know more algorithms for solving the
same problem, which of them shall you
implement?
 Answer: Analyze the algorithm

Department of Computer Science 15

 What does analysis of algorithm means?
 What is meant by Algorithm Analysis?
 Analysis of algorithms is the determination
of the amount of time and space resources
required to execute it.

Department of Computer Science

 Analysis of Algorithm
 How do we compare the time efficiency of
two algorithms that solve the same
problem?
 Naïve Approach/Experimental
Studies.
 Implement these algorithms in a
programming language (e.g. JAVA), and run
them to compare their time requirements.
 Theoretical/ mathematical Analysis
 Employ mathematical techniques that
analyze algorithms independently of specific
implementations, computers, or data.
 Scientific method applied to the
analysis of algorithms
Department of Computer Science 17
 Experimental Studies

 Write a program
implementing the
algorithm
 Run the program with
inputs of varying size
and composition
 Use a method like
System.currentTimeMillis() to
get an accurate
measure of the actual
running time
 Plot the results

Department of Computer Science 18

 Testing operation times on your system
import java.util.*;
public class PerformanceEvaluation {
public static void main(String[] args) {
int i=0; double d = 1.618;
SimpleObject o = new SimpleObject();
final int numLoops = 1000000;
long startTime = System.currentTimeMillis();;
for (i=0 ; i<numLoops ; i++){
// put here a command to be timed
}
long endTime = System.currentTimeMillis();
long duration = endTime - startTime;
double iterationTime = (double)duration / numLoops;
System.out.println("duration: "+duration);
System.out.println("sec/iter: "+iterationTime);
}}
class SimpleObject {
private int x=0;
public void m() { x++; }
}

Department of Computer Science

 Issues in experimental Approach
 Comparing the programs (instead of
algorithms) has difficulties.
 Programming language (e.g. MATLAB vs JAVA)
 The compiler you use(e.g. jdk1.1.8 vs jdk1.3.1)
 The OS on your computer( e.g. Window vs LINUX)
 Computer hardware(e.g. PII, 333MHz vs PIII,
500MHz)
 Programmer ability/ Programmer effectiveness
 Maybe other things: temperature outside; other
programs on your computer; …
 How to overcome these issues?
 i.e how we measure efficiency of an algorithm
instead of a program?
Department of Computer Science
 Complexity Analysis
 How we measure efficiency of an algorithm
instead of a program?
 Determine the computational complexity of
algorithms.
 Usually, this involves determining a function that
 relates the size of an algorithm's input to the number of
steps it takes (its time complexity).
 T(n) , C(n)
 relates the number of storage locations it uses (its space
complexity).
 Note: In this subject we only focus on time
complexity.
 Now how we determine time complexity
function, T(n)?
Department of Computer Science
 Complexity Analysis
 Now how we determine time complexity
function, T(n)?
 We can calculate time complexity in two
ways,
 first one being frequency count and the other
asymptotic notations.
 Frequency Count
 Since the number of operations is related to the
execution time, so will determine an equation that
relates the number of operations that a particular
algorithm performs to the size of the input.
 Frequency count specifies the number of times a
statement is to be executed
Department of Computer Science
 Complexity Analysis
 Frequency Count
 Frequency count specifies the number of times
a statement is to be executed.

Input size

T(n) ≈ cop × C(n)

# of times op.
Running time
Execution time is executed
for
operation

Department of Computer Science

 UPSHOT: Complexity Analysis
 Complexity analysis is useful for the following
two purposes:
 To decide the efficiency of the given algorithm.
 To compare algorithms for deciding the effective
solutions for a given problem.
 Advantages of computational complexity :
 Uses a high-level description of the algorithm instead
of an implementation
 Characterizes running time as a function of the input
size, n.
 e.g T(n) , C(n)
 Takes into account all possible inputs.
 Allows us to evaluate the speed of an algorithm
independent of the hardware/software environment.
Department of Computer Science
 Examples

Department of Computer Science

 The Execution Time of Algorithms

 Count the number of times each of an

algorithm’s operations is executed.
 Each operation in an algorithm (or a program)
has a cost.
 count = count + 1;  take a certain amount of time, but it is
constant

Department of Computer Science 26

 The Execution Time of Algorithms

 Consecutive Statements: Just add the running

times of those consecutive statements.
 A sequence of operations:

count = count + 1; Cost: c1

sum = sum + count; Cost: c2

 Total Cost = c1 + c2

Department of Computer Science 27

 The Execution Time of Algorithms

Example: Simple If-Statement

Cost Times
if (n < 0) c1 1
absval = -n c2 1
else
absval = n; c3 1

Total Cost = c1 + max(c2,c3)

Department of Computer Science 28

 Computing running time of Algorithms

Example: Simple Loop

Cost Times
i = 1; c1 1
sum = 0; c2 1
while (i <= n) { c3 n+1
i = i + 1; c4 n
sum = sum + i; c5 n
}
Total Cost = c1 + c2 + (n+1)*c3 + n*c4 + n*c5
Total Cost = c1 + c2 + n*c3 + c3 + n*c4 + n*c5
Total Cost = n*c3 + n*c4 + n*c5 + c1 + c2 + c3
Total Cost = n(c3+c4+c5)+ c1 + c2 +c3
Total Cost = An + B
Department of Computer Science
( A =c3+c4+c5 B= c1 + c2 +c29
3)
 Computing running time of Algorithms

Example: Simple Loop

Cost
Times
i = 1; c1 1
sum = 0; c2 1
while (i <= n) { c3 n+1
i = i + 1; c4 n

sum = sum + i; c5 n
}
Total Cost = An + B (This equation of straight line: y = mx + c)
 The time required for this algorithm is directly
proportional to n

Department of Computer Science 30

 The Computing running time of Algorithm

Example: Nested Loop

Cost Times
i=1; c1 1
sum = 0; c2 1
while (i <= n) { c3 n+1
j=1; c4 n
while (j <= n) { c5
n*(n+1)
sum = sum + i; c6 n*n
j = j + 1; c7 n*n
}
i = i +1; c8 n
}
Total Cost = c1 + c2 + (n+1)*c3 + n*c4
+n*(n+1)*c5+n*n*c6+n*n*c7+n*c8
Total Cost = An2 + Bn + C
 The
Department time Science
of Computer required for this algorithm is proportional to
31 n2
 The Computing running time of Algorithm
Cost Times
i=1; c1 1
sum = 0; c2 1
while (i <= n) { c3 n+1
j=1; c4 n
while (j <= n) { c5
n*(n+1)
sum = sum + i; c6 n*n
j = j + 1; c7 n*n
}
i = i +1; c8 n
}
Total Cost = An2 + Bn + C
 The time required for this algorithm is proportional to n2

Department of Computer Science 32

 General Rules for Estimation: SUMMARY

 Up Shot
 Consecutive Statements: Just add the running
times of those consecutive statements.
 If/Else: Never more than the running time of the
test plus the larger of running times of S1 and S2.
 Loops: The running time of a loop is at most the
running time of the statements inside of that loop
times the number of iterations.
 Nested Loops: Running time of a nested loop
containing a statement in the inner most loop is
the running time of statement multiplied by the
product of the sized of all loops.

Department of Computer Science 33

 Example: Linear Search

INPUT: a sequence of n numbers, key to search for.

OUTPUT: true if key occurs in the sequence, false
otherwise.

T(n) = c1 + c2*n + c3(n-1) + c4+c5+c6

 How to find cost(i.e. value of c1 to c2 etc.?

Department of Computer Science 34

 Model of Computation
(Assumptions)
 In order to determine cost of each instruction, we
assume that the algorithm is running on a standard
generic single-processor machine, called a Random
Access Machine(RAM)
 RAM is abstract computing model which is assumed
to be an idealized machine
 Infinitely large random-access memory
 Instructions execute sequentially
 Every instruction/operation in the machine's
memory takes unit time for execution.
 Example of basic operations include
 Assigning a value to a variable
 Arithmetic operation (+, - , × , /) on integers
 Performing any comparison e.g. a < b
 Boolean operations
 Accessing
Department of Computer Science an element of an array.
 Units for Measuring Running Time

 T(n) = c1 + c2*n + c3(n-1) + c4+c5+c6

According to RAM model(assumption),
 c = c =c = c =c = c =1
1 2 3 4 5 6
 T(n) = 1 + n+ n -1 +1+1+1
 T(n) = 2n +3

Department of Computer Science 36

 Complexity Analysis
 Is counting every operation that is
performed by
an algorithm useful?
 Let us discuss this with the help of the
following
example.
 Suppose we have an algorithm that counts
the number of different characters in a
file. An algorithm for that might look like
the following:

Department of Computer Science

 Complexity Analysis: what to count
 Is counting every operation that is
performed by
an algorithm useful?
 Let us discuss this with the help of the
following
example.
 Suppose we have an algorithm that counts
the number of different characters in a
file. An algorithm for that might look like
the following:

Department of Computer Science

 Complexity Analysis: what to count
 When we look at this algorithm, we see that
there are 256 iterations for the
initialization loop.
 If there are N characters in the input file,
there are N iterations for the second loop.
 So, the question becomes What do we
count?.
 In this algorithm we have following
operations:
 Assignments
 Conditional checks
 Increments
Department of Computer Science
 Complexity Analysis: what to count
Operatio Frequency count in for Frequency count in Total
n loop while loop
Assignmen 257 0 257
t (1 for the loop variable
and 256 for the counters)
Conditiona 257 N+1 N+258
l checks (257 checks that this (we will need to do a
variable is within the loop check of the condition N
bounds (the extra one is + 1 times the + 1 is for
when the loop stops) the last check when the
file is empty)
Increment 256 N N+ 256
(Increments of the loop (we will increment N
variable) counters.)
 The total operation that algorithm performed: 2N
 The purpose of for loop in
+771
this algorithm is to initialize
the counter. The total
operations performed in for
loop are: 770
Department of Computer Science
 Complexity Analysis: what to count
 So, if we have 500 characters in the file, the
algorithm will do a total of 1771 operations,
of which 770 are associated with the
initialization (43%).
 Now consider what happens as the value of
N gets large.
 If we have a file with 50,000 characters, the
algorithm will do a total of 100,771 operations, of
which there are still only 770 associated with the
initialization (less than 1% of the total work).
 The number of initialization operations has
not changed, but they become a much
smaller percentage of the total as N
increases.
Department of Computer Science
 Complexity Analysis: what to count
 The importance of the initialization is
small relative to the overall execution of
this algorithm.
In analysis terms, the cost of the initialization
becomes meaningless as the number of input
values increases.
 SO, WHAT TO COUNT AND CONSIDER?
 Deciding what to count involves two steps.
 The first is choosing the significant operation
or operations
 The second is deciding which of those
operations are integral to the algorithm and
which are overhead or bookkeeping.
Department of Computer Science
 Complexity Analysis: what to count
 Basic/Significant/Primitive Operation : the
most important operation of the algorithm,
the operation contributing the most to the
total running time.
 For example, the basic operation is usually
the most time-consuming operation in the
algorithm’s innermost loop.

Department of Computer Science

 Basic Operations
 There are two classes of operations that
are typically chosen for the significant
operation:
 Comparison
 Arithmetic
 Comparison operations include equal,
not equal, less than, greater than, less
than or equal, and greater than or equal.
 The comparison operators are all
considered equivalent and are counted
in algorithms such as searching and
sorting
Department of Computer Science
 Basic Operations
 We will count arithmetic operators in two
groups: additive and multiplicative.
 Additive Operators (usually called
additions for short) include addition,
subtraction, increment, and decrement.
 Multiplicative Operators (usually called
multiplications for short) include
multiplication, division, and modulus.
 These two groups are counted separately
because multiplications are considered to
take longer than additions.

Department of Computer Science

 Basic Operations
 logarithms and geometric functions that
are used in algorithms would be another
group.
 more time consuming than multiplications
because those are frequently calculated by a
computer through a power series.
 Shift operation, which is considered as fast
as an addition.
 There will be very few cases when this will be
significant, because multiplication or division
by 2 is commonly found in divide and conquer
algorithms that frequently have comparison as
their significant operation.
Department of Computer Science
 Examples

Department of Computer Science

 Basic Operations
 Basic operation/Primitive operation : the
most important operation of the
algorithm, the operation contributing the
most to the total running time.
Problem Basic operation

Searching for key in a list of n items Key comparison

Multiplication of two
Multiplication of two matrices
numbers

Checking primality of a given integer n Division

Visiting a vertex or
Typical graph problem
traversing an edge

Polynomial Evaluation multiplication

Department of Computer Science 48
 Example 1:

 What is its basic operation/Primitive

Operation?
 Multiplication(*)

Department of Computer Science

 Example 2:

 What is its basic operation/Primitive

Operation?
 Multiplication(*)

Department of Computer Science

 Example 3:

 What is its basic operation/Primitive

Operation?
 Multiplication(+)

Department of Computer Science

 Example 4:

 What is its basic operation/Primitive

Operation?
 Addition(+)

Department of Computer Science

 Example 5:

 What is its basic operation/Primitive

Operation?
 Division(/)

Department of Computer Science

 Example 6:

 What is its basic operation/Primitive

Operation?
 Comparison(>)

Department of Computer Science

 Example 7:

 What is its basic operation/Primitive

Operation?
 Comparison(=) A[i] = A[j]

Department of Computer Science

 Example 8:

 What is its basic operation/Primitive

Operation?
 Multiplication(*)

Department of Computer Science

 Growth Rate
 Let the frequency count of basic operation
of an algorithm is:
C(n) = n(n-1)/2
 How much fast C(n) grow if we double the
input size?
Ignore
 Solution cop,
Focus on
orders of
growth
 Since we are interested in the running time
for large input sizes, we may talk about the
rate of growth or the order of growth of the
running time.
Department of Computer Science
 Growth Rate
 A rate is a ratio that compares two
different quantities which have different
units.

Department of Computer Science

 Conclusion

Department of Computer Science

 What is
Complexity?
 The level of difficulty in solving
mathematically posed problems as
measured by
 The time
 (Time complexity)
 Number of steps or arithmetic operations
 (Computational complexity)
 Memory space required
 (Space complexity)
 What is Complexity function ?
 function that express these complexities
 We will focus on time complexity T(n):
 How to estimate the time required for an
algorithm
Department of Computer Science
 What does analysis of algorithm means?
 The analysis of algorithms is the process of
finding the computational complexity of
algorithms—the amount of time, storage, or
other resources needed to execute them.
 Usually, this involves determining a function:
 Count number of steps
 Count a particular operation
 T(input size) = frequency count of operation it takes*execution time of
the operation
 An algorithm is said to be efficient when this
function's values are small, or grow slowly
compared to a growth in the size of the input.

Department of Computer Science