Wednesday, 9 December 2015

Asymptotic Analysis - Part 1

Well, in our previous discussions, we found that how it is useful to study about algorithms. Now, let's dig down deeper. First, we want to know what does it mean to analyse an algorithm and  how do we do that ?

Analysis of Algorithms:  In computing, it is useful to know the complexity of any program will lead to solutions of some interesting questions like,

  • How long does it take to run a program with the given input set ?
  • How much space does it require to complete the problem ?
  • Is the problem solvable ?
Well, what do we do that having all those information ?
A good question indeed. To answer this question, let me take a hypothetical scenario of cleaning your house. You are in charge of cleaning your house and you have got some money in your hand to spend.

Now, what are the considerations, you want to do ?
  • How much time it should take to clean the house ?
  • What are the tools you should be using ?
  • When cleaning a room, do you need to shift all the furnitures in other room ?
  • Do you have enough space to shift the furnitures to other location ?
  • Is ir even possible to do that ?
So, you see, you are in a pretty good situation to take a decision on how to do that.

OK, let  me put some constraint on it, you have just one day to do that.

So, you are most probably to think in the direction where you will be vacating each room and clean that and again deploy all the furnitures you had in the room earlier.

Now, let me change the scenario, you have plenty of time and you have no extra room to clean your house, in that scenario, you mostly think of rearranging furnitures in the room and clean a part of the room and continue the stuff until the whole room gets clean and then you move to other room.

Now, let's put some serious condition that you have only one day and no extra room to clean your house.

What about this one ???

Well, its pretty complex to do that. I have to find a better way to do that.
Well, think of it...

Cool, I got some idea to do that, I will move my bed to ...
Congratulations !!! You have successfully found out the most efficient algorithm to clean your house.

Hey, but what does that relate to algorithm and computer science ? We do have plenty of resources nowadays. Quite fast CPU, Gigabytes of RAM. Why do we even care for time and space ?
Well, even with so fast computers and lots of resources, we are still in need of efficient algorithms and perform analysis of algorithms,

Let's talk about why we do that,

I had run a sorting algorithm which runs in a quadratic time (order of n2). So, as the input size grows larger, the running time grows quadratically and I had run the same sorting with another algorithm of order nlog(n).

If you take a look on previous article, you will find a table with run time of two different sorting algorithms with the same input set. You can obviously understand that, with 2.9 GHZ Processor Speed and dedicated 3 GB of RAM (Yes, I used 3 GB as the JVM Parameter for that program to run), the second algorithm (order of n2) failed to sort the numbers even after 9 days of execution while the first algorithm(order of nlogn), did that  in 8 seconds with an input size of only 50000000 numbers.

And sometimes, getting a correct answer late is considered as a wrong answer.

Well, that was a sort of test run against running time we can also have another parameter to test, the space usage. Many people use smartphones for day to day activities, may be some of you are reading this article on a smartphone or tablet. Many of the smartphones have less main memory than a desktop or laptop but in some scenarios, we are yet to perform the same set of operations on these devices too. So, in times, we have to think of the space usage along with the running time of the algorithms.

So, these are the basic needs of performing an analysis of algorithms where we take decisions which way to go. The situation is something like the below, where we have three sorting algorithms.

Conventions: Shorter line length means shorter running time, thicker line means more space usage.

So, we can see, that the first algorithm sorts the array in a long time with least memory usage and the third algorithm is fastest but it takes a greater memory footprint. While the second algorithm is efficient with a reasonable memory footprint. So, you need to understand, how much data is there, what are the expectation from the system.

That's all behind the decision making.

Now, we are in a good shape to understand that Analysis of Algorithms are necessary. Now let's see, how we can do that.

When analysing algorithms, we consider running time and space usage of a particular algorithm. For the time being, we'll just consider about the running time.
Now, to do that, we analyse on input size instead of,

  1. Running algorithms and measuring time, because for different machine the same algorithm can perform differently. Also, the programming language plays a key role in this.
  2. Count the steps in the  implementation, because the programming styles are different for different programmers.
As an alternative, we use Asymptotic Analysis to determine the complexity of an algorithm. Let's see what does this mean,

Asymptotic Analysis: Asymptotic  Analysis is a mathematical analysis which describes limiting behaviour.

In simple English, we can define that, it is a method of determine the rate of growth of running time as the input size grows.

So, we can tell that, if an algorithm runs in quadratically, then as the input grows in a linear fashion, the running time increases quadratically.

Well, that's all for now, we'll look into more depth in our subsequent articles.

Hope you enjoyed this article, happy learning...

No comments:

Post a Comment