Reading the index of the 1200 page beauty that is CLRS, I realized going in that completing all of it in a given period is not a practical goal. I read the preface first, to see how the authors want us to proceed. Reading it, I realized that I need some basic Algorithmic knowledge beforehand. I needed to learn about the Algorithm Analysis and the different Notations we use.
Why Algorithm Analysis?
Let’s talk about the Sorting problem. There are multiple ways to solve it. There’s Quick-sort, insertion sort, bubble sort, merge sort. Why do we need more than one methods to get the exact same end result?
The Answer to this lies behind the use of these sorting techniques. While all our sorting techniques to the same thing, when we use bubble-sort on an array of 1000 numbers, we discover how much extra time it takes, as compared to quick sort. This is but a small example, in case we have an even bigger set of data, the sorting time will increase exponentially, which will lead to not only an unpleasant User Experience (users hate lag!) but also increase the capacity of our program.
How to compare Algorithms?
Let’s first think of a couple different ways to compare algorithms,
- Execution Time: Not a good measure since the execution time would vary not only with the input, but also different computers.
- Number of statements executed: This is also an inefficient method, less number of statements do not necessarily mean faster algorithm. The same algorithm implemented in python might be smaller than in C. This does not mean that it is faster.
- Amount of time taken to design: While it may be considered for a moment that a well thought out algorithm should perform better, there is no guarantee that an algorithm designed quickly can not be effective or faster.