There is much to say, write and dream on an algorithms performance. Who can forget the BIG O notation taught in class? Except that, I did! Truth be told, I never quite understood it. Sure I could look at pseudo code and tell you its O(n^2), but I never quite got to the bottom of it. What was the BIG idea after all? So here I am, at the bottom of the stack, hoping to pop my way to the top. Eventually. I Hope.
The first What – What is performance?
Though one tends to immediately associate performance with ‘speed’ it needn’t be so. Performance can be a measure of any resource needed for the successful execution of an algorithm. It could be memory, or the number of communication messages that need to be sent across or it could simply be time. After all a sports car that is incredibly fast at speed and at consuming your precious hard earned fuel might not be your best bet for the cross country trip. Which brings us to the second question.
The Why – Why do we need to measure performance?
We need to measure performance to determine feasibility. Measuring the performance of your sports car helped you conclude that it was after all not a ‘feasible’ solution. How about your grandma’s trusted little van? Sure it takes you double the time to get to your local grocery. But that’s an additional 10 minutes, which doesn’t seem so bad. So now the road trip will take you 4 instead of the original 2 months you had in mind. Wait, what?
The second What – What affects performance?
Scaling affects performance. As the distance increased, the solution (grandma’s car) became less feasible. That is to say, the solution did not scale well. All was well as long as you had to visit the local groceries or even your aunt. In algorithmic terms, the algorithm gets slower as the input set gets larger. So to give you an example, if you wrote a sorting algorithm, it would take longer as the number of elements you had to sort got bigger. Which brings us to the ultimate question.
The cheeky How – How much longer?
Only the Big O is clever enough to answer that. Algorithm analysis is all about answering this question. When we measure an algorithms performance, we do not measure the actual time but instead its ‘growth’. If you do not quite understand this yet (like me), we shall look at it in detail in the upcoming blogs.