Why Analysis of
algorithms :
An algorithm is
a step by step procedure i.e. a set of instructions to solve the given problem.
For a problem there can be many algorithms to solve it. But how to find the
best algorithm among those?. Analysis of algorithms helps in determining the
solution for it.
What does it mean?
For example if
a person wants to travel from one place A to another place B, there can be many
routes to reach from A to B. Depending on the availability and convenience we
can choose the best route in terms of short route (if we want to reach fast),
Highway (Even though it is longer, but for convenience) etc.
Similarly in
Computer Science, there can be many algorithms for a same problem. Analysis of
algorithms helps us in determining which of them is efficient in terms of space
(memory) and running time by comparing the algorithms. But how to compare
algorithms ?
How to compare
algorithms ?
Running time is best
measure for comparing the algorithms. It is the process of determining the
processing time increases as the size of input size (problem) increases. Input
size may vary depending on the type of problems. In general we encounter the
following types of inputs.
1) Size of array
2) No of elements in the matrix
3) Polynomial degree
4) Vertices and edges in a graph
In
general, the running time of a algorithm is expressed as a function of input
size(n) i.e. f(n) and compare these functions corresponding with their running
times. This is independent of machine time, processor, programme style (no of
statements) etc.
Types of analysis :
To analyse the
algorithm, we need to represent the algorithm with multiple expressions: one for the case where it takes less
time and the other for the case
where it takes more time. The first case is called as Best case and the second case is called as Worst case for that algorithm. There are three types of analysis:
1) Best case
2) Average case
3) Worst case
For a given algorithm, we can represent the best, worst,
average cases in the form of expressions. For example
Let f(n) be the function represents the given
algorithm and n is the input size,
f(n) =
n2 + n + 100 ;
for worst case
f(n) =
5n + 200 ; for best case
The expressions defines the input for which the algorithm
takes the less or average time (or memory). If both best and worst cases,
points to one expression then that expression can be represented with average
case.
f(n) = 10n + 50 ; for best and
worst case
then f(n) can be represented for average case.
f(n) =
10n + 50 ; for average case
Adblock is enabled