Analysis of Algorithms
Q) What is an Algorithm?
·
An
algorithm is the step by step instructions to solve a given problem.
·
For
example, for preparing an omelet, generally steps we follow are
1. Get the frying pan.
2. Get the oil
3. Do we have an oil?
a. If Yes, put in pan.
b. If No, do we want to buy oil?
1. If Yes, go and buy oil
2. If No we can terminate
4. Turn on stove.
5. ……….. etc.
Q) Why performance analysis?
·
To go
from city ‘A’ to city ‘B’, there can be many ways
1. By Flight
2. By Bus
3. By Train
4. By Bicycle
·
Depending
on available convenience we will choose the best way to travel.
·
Similarly,
in computer science n number of algorithms are available to solve the problem,
we need to choose the algorithm based on our requirement.
·
Example,
to sort an array we have so many algorithms like insertion sort, selection
sort, quick sort.
·
So,
algorithm analysis will determine which one is efficient to use.
Q) Given two algorithms for a task, how do we find out which one is
better?
·
One
naive way of doing this is – implement both the algorithms and run the two
programs on your computer for different inputs and see which one takes less
time.
·
There
are many problems with this approach for analysis of algorithms.
o It might be possible that for some inputs, first algorithm
performs better than the second. And for some inputs second performs better.
o It might also be possible that for some inputs, first algorithm
performs better on one machine and the second works better on other machine for
some other inputs.
·
Asymptotic
Analysis is the big idea that handles
above issues in analysing algorithms.
Q) What is Asymptotic Analysis?
·
In
Asymptotic Analysis, we evaluate the performance of an algorithm in terms of
input size (we don’t measure the actual running time).
·
We
calculate, how does the time (or space) taken by an algorithm increases with
the input size.
·
For
example, let us consider the search problem (searching a given item) in a
sorted array.
o Linear Search (order of growth is linear)
o Binary Search (order of growth is logarithmic).
·
To
understand how Asymptotic Analysis solves the above mentioned problems in
analysing algorithms, let us say we run the Linear Search on a fast computer
and Binary Search on a slow computer.
·
For
small values of input array size n, the fast computer may take less time.
·
But, after
certain value of input array size, the Binary Search will definitely start
taking less time compared to the Linear Search even though the Binary Search is
being run on a slow machine.
·
The
reason is the order of growth of Binary Search with respect to input size
logarithmic while the order of growth of Linear Search is linear.
·
So, the
machine dependent constants can always be ignored after certain values of input
size.
Q) Does Asymptotic Analysis always work?
·
Asymptotic
Analysis is not perfect, but that’s the best way available for analysing
algorithms.
·
For
example, say there are two sorting algorithms that take 1000nLogn and 2nLogn time
respectively on a machine.
·
Both of
these algorithms are asymptotically same (order of growth is nLogn).
·
So,
With Asymptotic Analysis, we can’t judge which one is better as we ignore
constants in Asymptotic Analysis.
