In the previous blog post we started discussing what is an Algorithm and what are the properties of an algorithm. We will take that forward in this blog post where we will be discussing initial concepts of complexity analysis and at the same time, we will start knowing how to approach for algorithmic solution of a given problem
What is Complexity Analysis of Algorithm?
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?
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.
Let’s revisit Task 2 of the previous blog post (Let's Learn Algorithm - Part 1) to get an idea of how to approach a problem.
If I was at your
age and maturity, probably, I would have written the algorithm like the
following.
Algorithm: Freq_Word
Input: A word w
Output: character(s) c of w which has/have appeared most of the
time, get(s) printed.
Step 1: Take a character c of w one by one, and count how many times
it has appeared in w, let it be x
Step 2: Out of all x’s, find out
which one (or may be multiple) is maximum, print corresponding c
Step 3: End
Well, I am not
saying that this one is incorrect, but you need to always remember that as a
computer science professional, you will be writing algorithms for computers
which do not have any kind of natural intelligence. So, don’t you think that
this one is too abstract for a dumb machine?
Let us make it a
bit granular. To do so first let us understand our solution strategy as
depicted under with a demonstrative example where the word is “science”
But is this
strategy well enough? The answer is a big "no" as
it will print “c”, “e”, “c”, “e” instead of expected output “c” and “e”.
Let us revisit the
strategy once again, and try to find out, where lies the problem?
The letters “c” and
“e” are appearing twice as their frequencies have been computed two times, so
we should restrict computing frequencies of second instance of “c” and “e”, and
if we do this and at the same time if we could update the corresponding
placeholder value with an impossible value, let’s say -1, then during scanning
second “c” and “e” will not be picked up for printing.
But the question is
how we could restrict frequency computation of the non-first occurrence of a
character, in our case, second “c” and “e”.
To fix this issue, let's rewrite the algorithm in granular level.
Algorithm: Freq_Word
Input: A word w
Output: character(s) c of w which has/have appeared most of the time, get(s) printed.
Step 1: Calculate the length of w. let it be len.
Step 2: Create an array arr of length len and fill it up with some absurd value (say -1)
Step 3: for each c, if it is not an absurd character (say @), set a fresh counter cnt = 1 and do Step 4,
Step 4: for each forward character of c, (say c') if c' is equal to c, replace c' with @, increment cnt by 1 and update the current value of cnt to corresponding index of arr
Step 5: Scan arr and find the max value from arr (as discussed here)
Step 6: Scan arr once again, if any arr index matches with max value, print corresponding c from w
Step 7: End
In the next blog, we will discuss about Time Complexity Analysis of algorithms in simple words.
0 Comments