09-07-2012, 04:46 PM
DATA STRUCTURES AND ALGORITHMS MADE EASY
50658450-Data-Structures-and-Algorithms-Made-Easy-For-Interviews-Programming-Interview-Questions.pdf (Size: 1.72 MB / Downloads: 423)
Introduction
The objective of this chapter is to explain the importance of analysis of algorithms, their notations,
relationships and solving as many problems as possible. We first concentrate on understanding the
importance of analysis and then slowly move towards analyzing the algorithms with different notations and
finally, the problems. After completion of this chapter you should be able to find the complexity of any
given algorithm (especially recursive functions).
What is an Algorithm?
Just to understand better, let us consider the problem of preparing an omelet. For preparing omelet, general
steps which we follow are:
1) Get the frying pan.
2) Get the oil.
a. Do we have oil?
i. If yes, put it in the pan.
ii. If no, do we want to buy oil?
1. If yes, then go out and buy.
2. If no, we can terminate.
3) Turn on the stove, etc..
How to Compare Algorithms?
To compare algorithms, let us define some .
Execution times? as execution times are specific to a particular computer.
Number of statements executed? since the number of statements varies with the
programming language as well as the style of the individual programmer.
Ideal Solution?
Let us assume that we expressed running time of given algorithm as a function of the input size (i.e.,
). We can compare these different functions corresponding to running times and this kind of
comparison is independent of machine time, programming style, etc..
What is Rate of Growth?
The rate at which the running time increases as a function of input is called . Let us assume
that you went to a shop for buying a car and a cycle. If your friend sees you there and asks what you are
buying then in general we say This is because cost of car is too big compared to cost of cycle (
approximating the cost of cycle to cost of car).
Theta-θ Notation
This notation decides whether the upper and lower bounds of a given function (algorithm) are same or not.
The average running time of algorithm is always between lower bound and upper bound. If the upper
bound ( ) and lower bound ( ) gives the same result then notation will also have the same rate of
growth. As an example, let us assume that is the expression. Then, its tight upper bound
is . The rate of growth in best case is . In this case, rate of growths in best case and
worst are same. As a result, the average case will also be same. For a given function (algorithm), if the rate
of growths (bounds) for and are not same then the rate of growth case may not be same.
Important Notes
For analysis (best case, worst case and average) we try to give upper bound ( ) and lower bound ( ) and
average running time . From the above examples, it should also be clear that, for a given function
(algorithm) getting upper bound ( ) and lower bound ( ) and average running time ( ) may not be possible
always. For example, if we are discussing the best case of an algorithm, then we try to give upper bound ( )
and lower bound ( ) and average running time ( ).
In the remaining chapters we generally concentrate on upper bound ( ) because knowing lower bound ( )
of an algorithm is of no practical importance and we use notation if upper bound ( ) and lower bound ( )
are same.
Why is it called Asymptotic Analysis?
From the above discussion (for all the three notations: worst case, best case and average case), we can easily
understand that, in every case for a given function we are trying to find other function which
approximates at higher values of . That means, is also a curve which approximates at
higher values of . In mathematics we call such curve as . In other terms, is the
asymptotic curve for For this reason, we call algorithm analysis as .