COMPLEXGENE BLOG IS BACK ..... THIS WEEK: GOOD ALGORITHMS

Hi Guys,

How has been the weekend?

This week we will come with the basic concepts of Algorithmic Complexity(the initial steps of understanding how efficient an algorithm is).

Without understanding complexity its like writing a code without knowing a syntax.

I would try to make the things as simple as i can, assuming that after you read this blog you would start thinking about good algorithms for the first time in your life :).

Ok so here we go.................

Q1) What is an algorithm?

Ans: Mostly all will be able to answer this. Its a sequence of steps that perform a particular operation, or               rather designed to achieve some particular task.

So far so good.....

Q2) What is a good algorithm then?

Ans: Ah!! Come on shan(my nickname)!! Then why we would have been in this blog? :) Right...

        So, lets get to good algorithms. Now keep your brain smart for 5 mins for you are going to get the                 algorithmic complexity in your head very soon.

        Let suppose, we need to sort 5 numbers: 12  2  11 6 54, how will you sort?

        Lets make the sorting very simple, we go through each of the element 12 then 2 then 11 then 6 and then         54, pick the smallest among them, so we pick 2, then swap 2 with the element at first position.

        So now the arrangement would be: 2 12 11 6 54.

        We go again, swap the next smallest element with first position. Now it looks like: 2 6 11 12 54 and so         on.... Well we know that after some time the array would get sorted, but what we are concerned about is: Was this a good approach though we have accomplished our task, how much would it require?

Time?? What time?? Yeah... that's what we have to get concerned about when we are being able to do our task. We have to put forth a question that whether we could have been able to do it in less time with a better strategy?  Now what will be the time required. Is it 60 mins, is it 20 secs? Is it 5 mins..

No we don't talk of time in actual hours or minutes in algorithms. We talk of time in terms of number of elements on which we are doing any processing.

So let suppose insted of 5 elements there would have been 1,00,000 elements to be sorted.. so the numbers are not fixed, time to time it is going to change but we have to perform the same task on them... 

So lets make a standard, let us call the number of elements as N.

Ah!! that's fine as N is not fixed, it can be any number of elements according to the elements given  to us.

Sometime N=5, sometimes N=1,00,000.

So, now lets judge the algorithm we just discussed above for sorting:

Step 1: We are traversing all the elements and picking up the 1st smallest element out of them and then swapping it with element at first position. So to get the first smallest element we have traversed all the 'N' elements.

Step 2: For the next smallest we would need to traverse N-1 elements leaving the first position as it has already been replaced... 

Step 3: In this way to sort N elements in total we will get such a series of operation:

             ======>   N + (N-1) + (N-2) + (N-3)+..........+ 2 + 1   

             ======>   N(N+1)/2  ====> (N^2 + N)

       Ex: 1+2+3+4+5=15, similarly if N=5 then N(N+1)/2=(5*6)/2=30/2=15..... So in total we make 15 comparisons using our approach to sort 5 elements. You can manually count the number in sorting 5 elements above and you would get the same number.

Now we have understood how is the time measured... we will think of a better approach to make less comparisons for sorting N numbers.

Lets come back to the problem again..

I will try to make a better approach, you need correct me if i am wrong.. :)

Elements : 12  2  11 6 54

Step 1: We would traverse the whole array once and get the highest element from them. SO time taken is N as we are going through all the N elements.. and we get element as 54.

Step 2: We will make an array of size 54, say ARR[54] and then store each element to the corresponding index of the array, like 12 stored in ARR[12], 2 stored in ARR[2] and so on..so our array will look like:

So the array looks like this now..what to do next?

Oh yes!! One thing!! Don't think too much now as there can be elements with negative value, or an element such as zero.. After understanding you yourself try to figure out the solutions to such situations.

For now.. stick yourself to the limited Edition..  :D

So Next....

what to do?? Traverse the array from beginning and if we get a position not having 0, output that to the screen..

Starting from index 0.. we traverse... we output: 2 6 11 12 54 and voila!! That's sorted. :)

What time this time did we take?

Once we traversed the whole array through all elements to get the highest element: N

Next we traversed again through each N element to store them at corresponding index of the third array, again: N

Next, we traveled through the third array to output the elements in sorted order, again: N

So, we took 3*N time.

Okay!! So where the difference of it from the first algorithm,. Okay let suppose there are 20 elements in total.

Our first approach would take: 20(21)/2 = 210 unit time.

Our second approach would take: 3*20 = 60 unit time.

Oh!! yes!! See the difference when the number of elements is merely 20, just think of the difference when the number of elements will reach 1,00,000.

Okay!! Now i can breathe a bit as i can now assume that i have been able to make you understand what a good algorithm is and what its importance?

Today we will close here!! As now your mind is ready to think of ways to solve a problem in a better waqy, lets follow all the protocl of the algorithm in the next post and define the notion of BIG-O, BIG-OMEGA, and BIG-THETA :).. which sometimes become so confusing to various CS/IT champions.

Bye for now!! Will meet soon!! :)

Don't forget to add comments to cheer me up. :) Thank you all.