Algorithm Analysis
Why should we
analyze algorithms?
To predict the
resources that an algorithm requires (Time and Space)
Algorithm analysis:
·
Measures the efficiency of an algorithm in terms
of time and space requirements.
·
Compares the relative costs of two or more
algorithms to solve the same problem.
Let us understand with an example
There is list of n students with
their numbers and branches given.
We need to start all of them by their roll number. One way to do that is as shown here:
For I := 1 to n do
{
from
rollno[1] to rollno[n-1]
compare
pair-wise (each roll number with its next)
if
two consecutive roll numbers are out of order, swap them
}
Thus has ‘n’ iteration. Each iteration may take utmost n-1 comparisons and swaps (operations).
Hence, the number of operations
is in the order of n2
Now, let us say, we need to sort
the students by their branch instead of roll number. If there are ‘k’ branches,
branch 1 students have to be printed first followed by branch 2 and so on until
branch k.
If we use the previous algorithm,
we will again take the same number of operations.
Let us consider the following
algorithm instead.
Create
a sublist each for the ‘k’ branches, sublist 1 for branch 1, sublist 2 for
branch 2 etc.
for
I := 1 to n do
if
student[i] belongs to branch j, add him to sublist j.
print
the student detail in each sublist in the order of sublist 1, sublist 2,….
Sublist k.
This algorithm ha ‘n’ iterations
and each iteration has only one operation. So, the total number of operations
in the order of ‘n’.
Hence, it is important to analyze
the efficiency of an algorithm for different sizes and kinds of inputs.
Performance Analysis
Analysis of Algorithms
Analysis of algorithms is a
prediction of how fast the algorithm works based on the problem size.
·
When an algorithm is executed it uses the
computer’s primary memory (RAM) and Central Processing Unit(CPU).
·
Analyzing the amount of resources (time and
space) needed helps to choose a good algorithm among several options to solve
the same problem.
·
Analysis based on time taken to execute the
algorithm is called Tine Complexity of the Algorithm.
·
Analysis based on the memory required to execute
the algorithm is called Space Complexity of
the algorithm.
The analysis is done at two stages:
Priori Analysis (before developing the program):
This
involves analyzing the given algorithm, for various instances of the problem,
mathematically to find its time and space complexities.
Posteriori Analysis (after developing the program):
This
involves running the program for the given algorithm, for various instances of
the problem and tracking down the time and space required by them.
Differences between Priori and Posteriori analysis:
Priori
|
Posteriori
|
Program for the algorithm is not needed
|
Program for the algorithm is needed
|
It is machine independent
|
It is machine dependent
|
It is independent of language and skill of the
programmer
|
It depends on the skill of the person who codes
the algorithm and also the language in which the algorithm is coded.
|
This allows analyzing for any input instance
sizes.
|
This may permit testing for moderate input
instance sizes only.
|
Performance or Complexity of an
algorithm is measured by estimation the following two important factors.
Space Complexity:
The space complexity of a
computer program is the amount of memory required by it.
It varies with the size of the
problem being solved.
Reasons to study:
1. In
a multiuser system, we need to have an estimate of the amount of memory
required by the programs so that, memory allocation can be done efficiently.
2. It
is a good programming practice to know in advance, whether the available memory
is sufficient for the program to be executed
Calculation of Space Complexity:
·
The space S(p) needed to execute a program
depends on several factors (sizes of inputs and outputs, variables and other
objects etc.)
·
It can be approximated as follows
S(p) = C + SP
(I)
Where,
‘C’ is the fixed space requirement,
which is independent of the characteristics of the inputs and outputs.
·
It includes instruction space, space for
variable, constants etc.
‘I’ is the input size (e.g. the
number of elements to be sorted, the number of nodes in a graph traversal problem)
SP(I) is the variable space
requirement as a function of ‘I’
Example: Recursive function for multiplying a list of numbers.
Algorithm
RecursiveProduct(a, n)
{
if(n<=0)
then
return
0;
else
return
RecursiveProduct(a, n-1) * a[n];
}
Space required for the above
program:
·
Assume return address requires one word of space
·
Each call to RecursiveProduct takes three words
space, for the value of ‘n’ , the pointer to ‘a’ and the return address.
·
The number of calls made to RecursiveProduct is
‘n+1’
·
Therefore space required by the above algorithm
is S(P) >= 3(n+1).
Time Complexity:
Time complexity is usually the
amount of time it takes to run a program as a function of the size of the
input.
Reasons to study:
1. While creating software
applications there is often a need to judge how quickly a program can execute.
2. We can use the time complexity
to estimate the maximum throughput time.
Calculation of Time complexity:
·
Time complexity of an algorithm has two
components, the compilation time and the execution time. The compilation time is independent of the
nature and size of the input. The execution time however, depends on the size
and nature of the input data..
·
The time taken ‘T’ by a program ‘P’
T(P) = C +
TP(I)
Where,
· ‘C’ is the compilation time, which is
independent of the instance characteristics (e.g. input size)
·
‘I’ is the input size (e.g. the number of
elements to be stored, the number of nodes in a graph traversal problem).
·
TP(I) is execution time i.e. the sum of time
required to perform various operation like addition, subtractions and
multiplications present in the program. It is typically expressed as a function
of ‘I’
