Performance Analysis of an Algorithm
What is Performance Analysis of an algorithm?
If we want to go
from city "A" to city "B", there can be many ways of doing
this. We can go by flight, by bus, by train and also by bicycle. Depending on
the availability and convenience, we choose the one which suits us. Similarly,
in computer science, there are multiple algorithms to solve a problem. When we
have more than one algorithm to solve a problem, we need to select the best
one. Performance analysis helps us to select the best algorithm from multiple
algorithms to solve a problem.
When there are multiple alternative algorithms to solve a problem, we analyze
them and pick the one which is best suitable for our requirements. The formal
definition is as follows...
Performance of an
algorithm is a process of making evaluative judgement about algorithms.
It can also be
defined as follows...
Performance of an
algorithm means predicting the resources which are required to an algorithm to
perform its task.
That means when we
have multiple algorithms to solve a problem, we need to select a suitable
algorithm to solve that problem.
We compare algorithms with each other which are solving the same problem, to
select the best algorithm. To compare algorithms, we use a set of parameters or
set of elements like memory required by that algorithm, the execution speed of
that algorithm, easy to understand, easy to implement, etc.,
Generally, the performance of an algorithm depends on the following elements...
1.
Whether that algorithm is providing
the exact solution for the problem?
2.
Whether it is easy to understand?
3.
Whether it is easy to implement?
4.
How much space (memory) it requires
to solve the problem?
5.
How much time it takes to solve the
problem? Etc.,
When we want to
analyse an algorithm, we consider only the space and time required by that
particular algorithm and we ignore all the remaining elements.
Based on this information, performance analysis of an algorithm can also be
defined as follows...
Performance
analysis of an algorithm is the process of calculating space and time required
by that algorithm.
Performance
analysis of an algorithm is performed by using the following measures...
1.
Space required to complete the task
of that algorithm (Space Complexity). It includes program space and data space
2.
Time required to complete the task of
that algorithm (Time Complexity)
What is Space complexity?
When we design an
algorithm to solve a problem, it needs some computer memory to complete its
execution. For any algorithm, memory is required for the following purposes...
1.
To store program instructions.
2.
To store constant values.
3.
To store variable values.
4.
And for few other things like funcion
calls, jumping statements etc,.
Space complexity of
an algorithm can be defined as follows...
Total amount of
computer memory required by an algorithm to complete its execution is called as
space complexity of that algorithm.
Generally, when a
program is under execution it uses the computer memory for THREE reasons. They
are as follows...
1.
Instruction Space: It is the amount of memory used to store compiled version of
instructions.
2.
Environmental
Stack: It is the amount of memory used to store
information of partially executed functions at the time of function call.
3.
Data Space: It is the amount of memory used to store all the variables and
constants.
Note - When we want to perform analysis of
an algorithm based on its Space complexity, we consider only Data Space and
ignore Instruction Space as well as Environmental Stack.
That means we calculate only the memory required to store Variables, Constants,
Structures, etc.,
To calculate the
space complexity, we must know the memory required to store different datatype
values (according to the compiler). For example, the C Programming Language
compiler requires the following...
1.
2 bytes to store Integer value.
2.
4 bytes to store Floating Point
value.
3.
1 byte to store Character value.
4.
6 (OR) 8 bytes to store double value.
Consider the
following piece of code...
Example 1
int square(int a)
{
return a*a;
}
In the above piece
of code, it requires 2 bytes of memory to store variable 'a' and another 2
bytes of memory is used for return value.
That means, totally it requires 4 bytes of memory to complete its
execution. And this 4 bytes of memory is fixed for any input value of 'a'. This
space complexity is said to be Constant Space Complexity.
If any algorithm
requires a fixed amount of space for all input values then that space
complexity is said to be Constant Space Complexity.
Consider the
following piece of code...
Example 2
int sum(int A[ ],
int n)
{
int sum = 0, i;
for(i = 0; i <
n; i++)
sum = sum + A[i];
return sum;
}
In the above piece of code it
requires
'n*2' bytes of memory to store array variable 'a[ ]'
2 bytes of memory for integer parameter 'n'
4 bytes of memory for local integer variables 'sum' and 'i' (2 bytes
each)
2 bytes of memory for return value.
That means, totally it requires
'2n+8' bytes of memory to complete its execution. Here, the total amount of
memory required depends on the value of 'n'. As 'n' value increases the space
required also increases proportionately. This type of space complexity is said
to be Linear Space Complexity.
If the amount of
space required by an algorithm is increased with the increase of input value,
then that space complexity is said to be Linear Space Complexity.
Time Complexity
What is Time complexity?
Every algorithm requires some amount
of computer time to execute its instruction to perform the task. This computer
time required is called time complexity.
The time complexity of an algorithm can be defined as follows...
The time complexity of an algorithm is the total amount of time required
by an algorithm to complete its execution.
Generally, the
running time of an algorithm depends upon the following...
1.
Whether it is running on Single processor
machine or Multi processor machine.
2.
Whether it is a 32 bit machine
or 64 bit machine.
3.
Read and Write speed of the machine.
4.
The amount of time required by an
algorithm to perform Arithmetic operations, logical operations, return value
and assignment operations etc.,
5.
Input data
Note - When we calculate time complexity of
an algorithm, we consider only input data and ignore the remaining things, as
they are machine dependent. We check only, how our program is behaving for the
different input values to perform all the operations like Arithmetic, Logical,
Return value and Assignment etc.,
Calculating Time
Complexity of an algorithm based on the system configuration is a very
difficult task because the configuration changes from one system to another
system. To solve this problem, we must assume a model machine with a specific
configuration. So that, we can able to calculate generalized time complexity
according to that model machine.
To calculate the time complexity of an algorithm, we need to define a model
machine. Let us assume a machine with following configuration...
1.
It is a Single processor machine
2.
It is a 32 bit Operating System
machine
3.
It performs sequential execution
4.
It requires 1 unit of time for
Arithmetic and Logical operations
5.
It requires 1 unit of time for
Assignment and Return value
6.
It requires 1 unit of time for Read
and Write operations
Now, we calculate
the time complexity of following example code by using the above-defined model
machine...
Consider the
following piece of code...
Example 1
int sum(int a, int
b)
{
return a+b;
}
In the above sample
code, it requires 1 unit of time to calculate a+b and 1 unit of time to return
the value. That means, totally it takes 2 units of time to complete its
execution. And it does not change based on the input values of a and b. That
means for all input values, it requires the same amount of time i.e. 2 units.
If any program requires a fixed amount of time for all input values then
its time complexity is said to be Constant Time Complexity.
Consider the
following piece of code...
Example 2
int sum(int A[],
int n)
{
int sum = 0, i;
for(i = 0; i < n; i++)
sum = sum + A[i];
return sum;
}
For the above code,
time complexity can be calculated as follows...
In above calculation
Cost is the amount of computer time required for a single operation in
each line.
Repeatation is the amount of computer time required by each operation for all
its repeatations.
Total is the amount of computer time required by each operation to
execute.
So above code requires '4n+4' Units of computer time to complete the task. Here the exact time is not
fixed. And it changes based on the n value. If we increase the n value then
the time required also increases linearly.
Totally it takes '4n+4' units of time
to complete its execution and it is Linear Time Complexity.
If the amount of time required by an algorithm is increased with the
increase of input value then that time complexity is said to be Linear Time
Complexity.
Comments
Post a Comment