Unit 2 Fundamentals of the Analysis of
Algorithm Efficiency
Structure:
2.1 Introduction
Objectives
2.2 Algorithm Analysis Framework
Complexity of algorithm
Measuring an input size
Measuring running time
Best case, worst case and average case analysis
2.3 Methodologies for Analyzing Algorithms
Pseudocode
Random access machine (RAM) model
Counting primitive operations
Analyzing recursive algorithms
2.4 Amortization
Amortization techniques
Analyzing an extendable array implementation
2.5 Case Studies in Algorithm Analysis
A quadratic time prefix averages algorithm
A linear- time prefix averages algorithm
2.6 Summary
2.7 Glossary
2.8 Terminal Questions
2.9 Answers
2.1 Introduction
In the previous unit we studied about the basics of algorithm and data
structures. In this unit we will discuss analysis of algorithm efficiency.
is an important part of computational
Algorithm analysis complexity theory. It
provides theoretical estimates for the resources needed for any algorithm to
solve a given problem. These estimates help to provide an insight regarding
the measures that determine algorithm efficiency.
This unit covers algorithm analysis framework with respect to complexity of
an algorithm. It gives an idea about various methods used for analyzing
, algorithms and explains the techniques involved in amortization. It also
includes some case studies in algorithm analysis.
Objectives:
After studying this unit you should be able to:
define algorithm analysis framework
explain different methods for analyzing the algorithms
describe amortization analysis
in algorithm
2.2 Algorithm Analysis Framework
Algorithm analysis framework involves finding out the time taken by a
program and the memory space it requires to execute. It also determines
how the input size of a program influences the running time of the program.
2.2.1 Complexity of algorithm
We can determine the efficiency of an algorithm by calculating its
performance. The two factors that help us to determine the efficiency of an
algorithm are:
Amount of time required by an algorithm to execute
Amount of space required by an algorithm to execute
These are generally known as time complexity and space complexity of an
algorithm.
Time complexity
Time complexity of an algorithm is the amount of time
required for it to
execute.
The time taken by an algorithm is given the sum of the
as
compile time and
the execution time. The compile time does not depend
the instance on
characteristics as a program once complied can be run
many times without
recompiling. So only the run time of the program matters while
calculating
time complexity and it is denoted by t, (instance
characteristics).
It is difficult to calculate the time
complexity in terms of
physically clocked
time
For example in multi-user operating system, it depends on various factors
such as:
Systemload
Number of programs running on the system
, Instruction set used
Speed of the hardware
The time complexity of an algorithm is given in terms of frequency counts.
Frequency count is the count that indicates the number of times the
statement is executed.
Space complexity
Space complexity of an algorithm is the amount of storage required for it to
execute.
The space required by an algorithm to execute is given as the sum of the
following components:
1) A fixed part that is independent of the characteristics of inputs and
output. This part includes instruction space (for example space for the
code), space for simple variables and fixed size component variables
and space for constants.
2) A variable part that consists of the space needed by the component
variables whose size is dependent on a particular problem instance
being solved and the space needed by the referenced variable.
Therefore to calculate the space complexity of an algorithm we have to
consider two factors:
Constant characteristic
Instance characteristic
Equation 2.1 depicts the space requirement S(p) of an algorithm.
S(p) C +Sp Eq: 2.1
Where C is the constant part and indicates the space required for inputs and
outputs which includes instructions, variables and identifiers.
S defines the space required for an instance characteristic. This is a
variable part whose space requirement depends on a particular problem.
2.2.2 Measuring input size
The time required to execute an algorithm depends on the input size of the
algorithm. If the input size is longer, then the time taken to execute it is
more. Therefore we can calculate the efficiency of an algorithm as a function
to which the input size is passed as a parameter.
Algorithm Efficiency
Structure:
2.1 Introduction
Objectives
2.2 Algorithm Analysis Framework
Complexity of algorithm
Measuring an input size
Measuring running time
Best case, worst case and average case analysis
2.3 Methodologies for Analyzing Algorithms
Pseudocode
Random access machine (RAM) model
Counting primitive operations
Analyzing recursive algorithms
2.4 Amortization
Amortization techniques
Analyzing an extendable array implementation
2.5 Case Studies in Algorithm Analysis
A quadratic time prefix averages algorithm
A linear- time prefix averages algorithm
2.6 Summary
2.7 Glossary
2.8 Terminal Questions
2.9 Answers
2.1 Introduction
In the previous unit we studied about the basics of algorithm and data
structures. In this unit we will discuss analysis of algorithm efficiency.
is an important part of computational
Algorithm analysis complexity theory. It
provides theoretical estimates for the resources needed for any algorithm to
solve a given problem. These estimates help to provide an insight regarding
the measures that determine algorithm efficiency.
This unit covers algorithm analysis framework with respect to complexity of
an algorithm. It gives an idea about various methods used for analyzing
, algorithms and explains the techniques involved in amortization. It also
includes some case studies in algorithm analysis.
Objectives:
After studying this unit you should be able to:
define algorithm analysis framework
explain different methods for analyzing the algorithms
describe amortization analysis
in algorithm
2.2 Algorithm Analysis Framework
Algorithm analysis framework involves finding out the time taken by a
program and the memory space it requires to execute. It also determines
how the input size of a program influences the running time of the program.
2.2.1 Complexity of algorithm
We can determine the efficiency of an algorithm by calculating its
performance. The two factors that help us to determine the efficiency of an
algorithm are:
Amount of time required by an algorithm to execute
Amount of space required by an algorithm to execute
These are generally known as time complexity and space complexity of an
algorithm.
Time complexity
Time complexity of an algorithm is the amount of time
required for it to
execute.
The time taken by an algorithm is given the sum of the
as
compile time and
the execution time. The compile time does not depend
the instance on
characteristics as a program once complied can be run
many times without
recompiling. So only the run time of the program matters while
calculating
time complexity and it is denoted by t, (instance
characteristics).
It is difficult to calculate the time
complexity in terms of
physically clocked
time
For example in multi-user operating system, it depends on various factors
such as:
Systemload
Number of programs running on the system
, Instruction set used
Speed of the hardware
The time complexity of an algorithm is given in terms of frequency counts.
Frequency count is the count that indicates the number of times the
statement is executed.
Space complexity
Space complexity of an algorithm is the amount of storage required for it to
execute.
The space required by an algorithm to execute is given as the sum of the
following components:
1) A fixed part that is independent of the characteristics of inputs and
output. This part includes instruction space (for example space for the
code), space for simple variables and fixed size component variables
and space for constants.
2) A variable part that consists of the space needed by the component
variables whose size is dependent on a particular problem instance
being solved and the space needed by the referenced variable.
Therefore to calculate the space complexity of an algorithm we have to
consider two factors:
Constant characteristic
Instance characteristic
Equation 2.1 depicts the space requirement S(p) of an algorithm.
S(p) C +Sp Eq: 2.1
Where C is the constant part and indicates the space required for inputs and
outputs which includes instructions, variables and identifiers.
S defines the space required for an instance characteristic. This is a
variable part whose space requirement depends on a particular problem.
2.2.2 Measuring input size
The time required to execute an algorithm depends on the input size of the
algorithm. If the input size is longer, then the time taken to execute it is
more. Therefore we can calculate the efficiency of an algorithm as a function
to which the input size is passed as a parameter.
