Algorithm Analysis & Performance – 2 Whats a Why and a cheeky How

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.

Advertisements

2 thoughts on “Algorithm Analysis & Performance – 2 Whats a Why and a cheeky How

  1. All of your 3 homely non compsci readers just got a rude shock @ a post they can’t even begin to comprehend !!!! Evidenced by the absence of comments.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s