Today, I had a discussion with my colleague (Raveendra Chikkala), about Data Structures. It was a really interesting and motivating discussion, and today I wanted to share it with all of you. I have never taken the complexities of the algorithms seriously till date in my day to day programming, though I cared a lot on the design patterns and worked hard on making the system loosely coupled and having high cohesion.
Gist of the discussion is as follows:
Me: Why do we need to think of Data Structures, what do you mean by Data Structures. I know we use the data structures to store the data, and faster retrieval.
Friend: Yes, Data Modeling and Retrieving, is all about data structures, but we need to consider the complexity of the programs we write in every day programming, if we just use the data structures, and not considering the complexity of your own code is wrong. Predefined Data Structures, follows a set of algorithms, so that the data retrieval and update functions will be of high performance. While, it is also our responsibility to have good performance of the code we write.
Below is the example, he gave to justify his statement.
For Example Consider two lists List1 having some elements and L2 is having some elements. Now try to find the intersection of these two lists.
He calculated the complexity of my logic as Looping n times in List1 will have a complexity of “N”, and complexity of contains() method on List2 is “N”, then the complexity of the logic above becomes N*N = N2 , which means the complexity increases exponentially. Consider each List is having 1 Million objects then the complexity will become 1000 Billion calculations.
The above algorithm will have the complexity as follows, as Collections.sort() uses merge sort technique, and its complexity is given as “nlogn” since we are calling Collections.sort() method twice on 2 lists the complexity will be “2*nlogn” . The looping will have the complexity of “n” and as the binary search is having the complexity of “log(n)”. Hence the complexity of the loop becomes “n*logn”. So the total complexity of the system will be “2*nlogn +n*logn”. Which is a Linear complexity. Considering each List is having 1 Million objects then the complexity will become “(2*106*2.5)+(106*2.5) = 7.5” Million calculations.
So, his solution of getting an intersection of two lists is far far far…. better than my way. I was shocked to see this, and understood the importance of understanding the complexity of the algorithms we write in day to day programming matters more than we can ever think.
If you did started thinking like me, that whatever quick solves you did in day to day programming as dirty code, then I am sharing some of the references he pointed to me in references link. Please go and have a read of those. Otherwise, also thanks for you patience and interest in reading till now, and am sure one day or the other you will find it important and come back again.
In addition to this, I learnt the importance of Mathematics, and Progressions in programming, and am now confident of saying a good mathematician with a passion to program will become the “Real Developer of the World”. I did resolute to become more realistic developer, now its your turn.
Raveendra Profile : http://in.linkedin.com/pub/raveendra-ch/2b/795/b5a/
Bill Gates on Programming : http://programmersatwork.wordpress.com/bill-gates-1986/