What is Complexity Analysis of Algorithm?
Complexity Analysis, simply put,
is a technique through which you can judge about how good one particular
algorithm is. Now the term “good” can mean many things at different times.
Suppose you have to go from your
home to the Esplanade! There are many ways from your home that may lead to
Esplanade. Take any one, and ask whether this route is good or bad. It may so
happen that this route is good if the
time of travel is concerned (that is the route is short enough), but at the
same time, it may be considered bad
taking the comfort into considerations (This route may have many speed breakers
leading to discomforts). So, the goodness (or badness as well) of any solution
depends on the situations and whatever is good
to you right now, may seem as bad if
the situation changes. In a nutshell, the goodness/badness or the efficiency of
a particular solution depends on some criteria of measurements.
So what are the criteria while analyzing complexities of algorithms?
Focusing only on algorithms, the
criteria are Time and Space. The criteria Time, judges how fast or slow the algorithms run when executed; and
the criteria Space judges how big or
small amount of memory (on primary/hard disks) is required to execute the
algorithm. Depending on these two measuring criteria, two type of Algorithm
Analysis are done; one is called Time
Complexity Analysis and the second one is Space Complexity Analysis.
Which one is more important over the other?
I am sorry! I do not know the answer;
rather there is no straight forward answer to this question. Think of yourself.
Thinking of the previous example of many solutions that you have for travelling
from your home to Esplanade, which criteria is most important? Is it Time of Travel, or is it Comfort? Or is it Financial Cost? It depends actually. While you are in hurry for
shopping at New Market, the Time Taken
would probably be your choice. If you have enough time in your hand, if you are
in jolly mood and if you are going for a delicious dinner with your friends,
probably you would choose Comfort;
and at the end of the month, when you are running short with your pocket money,
the Financial Cost would be most
important to you. So the most important
criterion is a dynamic notion that evolves with time.
Twenty or thirty years back, when
the pace of advancement of Electronics and Computer Hardware was timid, computer
programs were forced to run with lesser amount of memory. Today you may have gigantic memory even as
RAM, but that time, thinking of a very large hard disk was a day dreaming! So
at that time, Space Complexity was
much more important than the Time
Complexity, because we had lesser memory but ample times.
Now the time has changed! Now a
day, we generally enjoy large memories but sorry, we don’t have enough time with
us. We need every program to run as quick as possible! So currently, Time Complexity wins over Space Complexity. Honestly, both of these options are equally
important from theoretical perspective but the changing time has an effect to
these.
