Comparing Algorithms
I recently mentioned that MIT OpenCourseware project started hosting Video/Audio lectures as well for some select courses. Thats an excellent opportunity to go to MIT and take a class without ever leaving your home.
I never studied formally about Computer Algorithms. So I started taking the course : 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005. After spending so many years in Software Development, I must admit, I have not much to take away from the first 1 hour 20min class, but here are some thoughts and notes on the size of input.
[Source:Wiki] In theoretical analysis of algorithms it is common to estimate their complexity in asymptotic sense, i.e., to estimate the complexity function for reasonably large length of input. Big O notation, omega notation and theta notation are used to this end. For instance, binary search is said to run an amount of steps proportional to a logarithm, or in O(log(n)), colloquially "in logarithmic time". Usually asymptotic estimates are used because different implementations of the same algorithm may differ in efficiency. However the efficiencies of any two "reasonable" implementations of a given algorithm are related by a constant multiplicative factor called hidden constant.
The key aspect of Asymptotic analysis is about estimating the rate of growth of required resources to achieve a function, particularly, to estimate the complexity function for reasonably large length of input. If the size of input doesn't qualify for this reasonably large length of input then the analysis just doesn't apply. Then the big question is about knowing this size of input, to be able to apply the concept for each such algorithm. This is the missing piece of the puzzle, often ignored. Often, it was always argued that one algorithm is much better than the other, as that is what being taught in class room or mentioned in academics.
For general problems like sorting, we might get an extensive analysis available in books and papers. But when it comes to problems that are specific to a domain, there is not much analysis available. We must do on our own to find out what is a resonably large size of input means for our problem. If we can learn how to do this, then we can apply our understanding of Asymptotic analysis in real life problems.
This is the reason we might have multiple algorithms in a solution rather than having just the 'BEST' (as per some CS grads) algorithm.
The example being discussed in the class was about sorting. Two algorithms have been compared: Insertion Sort and Merge Sort. Watch lecture 1 here. Link to Thought Garage » MIT Video/Audio OpenCourseWare
Comments
Keep Clicking,
Bhasker