Lecture # 18 - New

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

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 choose an algorithm for an application.
Algorithm Design and Analysis Process
Understand the problem
Decide on : algorithm
design techniques etc.
Design an algorithm

Decide
Decideonon:algorithm
algorithm
Design an algorithm
Prove correctness

Design an algorithm
Prove correctness
Analyze efficiency etc.

Design an algorithm
Prove correctness
Analyze efficiency etc

efficiency
Code the algorithm
Analysis of Algorithm
Lecture No 5
Fundamentals of the Analysis of

Algorithm Efficiency
(Analysis Framework.)

Reading Material
Read Chapter 2
Fundamentals of the Analysis
of Algorithm Efficiency

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

MOTIVATION
Why performance analysis?

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?

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

 Answer: Analyze the algorithm
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.

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

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

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++; }
}

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?
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)?
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

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 for is executed
operation

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.
Examples

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

 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

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)

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
( A =c3+c4+c5 B= c1 + c2 +c3) 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 = An + B (This equation of straight line: y = mx + c)
 The time required for this algorithm is directly
proportional to n

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 required
of Computer Science for this algorithm is proportional to n2 30
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

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.

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.?

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 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

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:

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:

 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

Operation Frequency count in for Frequency count in while Total
loop loop
Assignment 257 0 257
(1 for the loop variable and
256 for the counters)
Conditional 257 N+1 N+258
checks (257 checks that this variable (we will need to do a check
is within the loop bounds (the of the condition N + 1 times
extra one is when the loop the + 1 is for the last check
stops) 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 +771
 The purpose of for loop in
this algorithm is to initialize
the counter. The total
operations performed in for
loop are: 770
 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.
 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.
 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.

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

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.

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.

Examples

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

Example 1:
 What is its basic operation/Primitive Operation?

 Multiplication(*)

Example 2:


Example 3:

 Multiplication(+)

Example 4:

 Addition(+)

Example 5:

 Division(/)

Example 6:

 Comparison(>)

Example 7:

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

Example 8:


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 cop,
 Solution 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.
Growth Rate
 A rate is a ratio that compares two different
quantities which have different units.

Conclusion

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
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.

Lecture # 18 - New

Uploaded by

Copyright:

Available Formats

Lecture # 18 - New

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture # 18 - New

Uploaded by

Copyright:

Available Formats

Design and Analysis of Algorithm

Tanveer Ahmed Siddiqui

Department of Computer Science

Department of Computer Science 2

Department of Computer Science

 How we design an algorithms?

Understand the problem

Department of Computer Science

Department of Computer Science

Analyze efficiency etc.

Department of Computer Science

Analyze efficiency etc

Fundamentals of the Analysis of

Department of Computer Science

Department of Computer Science

After completing this lecture, you will be able to

Department of Computer Science

Department of Computer Science

Department of Computer Science 13

 Which algorithm is best? Sort_A or Sort_B

 What is meant by Algorithm Analysis?

Department of Computer Science

Department of Computer Science 16

Department of Computer Science 17

Department of Computer Science

Department of Computer Science

T(n) ≈ cop × C(n)

Department of Computer Science

Department of Computer Science

 Count the number of times each of an algorithm’s

Department of Computer Science 25

 Consecutive Statements: Just add the running times

count = count + 1; Cost: c1

Department of Computer Science 26

Example: Simple If-Statement

Total Cost = c1 + max(c2,c3)

Department of Computer Science 27

Example: Simple Loop

Example: Simple Loop

Department of Computer Science 29

Example: Nested Loop

Department of Computer Science 31

Department of Computer Science 32

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

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

Department of Computer Science 33

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

Department of Computer Science 35

 Is counting every operation that is performed by

Department of Computer Science

 Is counting every operation that is performed by

Department of Computer Science

Department of Computer Science

Department of Computer Science

Department of Computer Science

Department of Computer Science

Department of Computer Science

Department of Computer Science

 Basic operation/Primitive operation : the most