Don't ask to ask, just ask | |
PerlMonks |
You may have already read An informal introduction to O(N) notation by dws which is excellent. This tutorial will repeat much of the same information in a much more elementary manner as well as go into detail about how useful or not the notation is. It is likely I won't be completely accurate about a number of things in the tutorial. My hope is that by the end, your understanding of the topic will be sufficient enough that you can understand the corrections others make (as I am sure they will).
It is easy to lose sight of the fact that there is more to consider about an algorithm other than how fast it runs. The Big-O can also be used to describe other behavior such as memory consumption. We often optimize by trading memory for time. You may need to choose a slower algorithm because it also consumes less of a resource that you need to be frugal with.
This is O(N^2). After a little bit of testing we decide that this is far too slow, so we make a little optimization.for my $i (0 .. $#array) { for my $j (0 .. $#array) { next if $j == $i; # Compare $i, $j } }
We have just cut our run time in half - YAY! Guess what, the Big-O has stayed the same O(N^2). This is because N^2 / 2 only has one variable part. The divided by 2 remains the same (constant) regardless of the input size. There are valid mathematical reasons for doing this but it can be frustrating to see two algorithms with the exact same Big-O that results in one running twice as fast as the other.for my $i (0 .. $#array - 1) { for my $j ($i + 1 .. $#array) { # Compare $i, $j } }
Implementation Details: The Big-O is an uncaring cold-hearted jerk. It does not care if you can't afford to buy the extra RAM needed for your problem and have to resort to tying your hash to disk. You are on your own. It also doesn't care that the data structure you would need to implement to achieve O(Log Log N) is so complex you will never be able to maintain it. In a nutshell, the Big-O lives in the land of theory and doesn't care very much about the real world.
Let's consider using cacheing as an optimization. In theory, the Big-O is going to ignore it saying your input is all different and you will never benefit from it. In reality, you test it and discover that you have a 60% hit rate. You do a little more experimenting and discover that the input size required for a more complex algorithm to be faster is larger than your real maximum input size. This all despite the more complex alorithm having a more favorable Big-O.
In a nutshell, the Big-O of a given algorithm combined with the specific problem knowledge is a great way to choose the best algorithm for your situation.
I have not really added anything to any of the other links I referenced. I do hope however that I have put it in plain enough english to be understood by even the most extreme novice. I welcome those more knowledgeable than myself to add corrections as well as provide additional content. I would only ask that you do so in the same spirit of this tutorial (understandable by non-CS majors).
Update: Removed an incorrect analogy regarding slopes thanks to blokhead.Cheers - L~R
|
---|
Replies are listed 'Best First'. | |
---|---|
Re: Big-O Notation - What is it good for?
by blokhead (Monsignor) on Sep 15, 2006 at 17:54 UTC | |
by Anonymous Monk on Jul 10, 2008 at 14:34 UTC | |
by jpearl (Scribe) on Mar 13, 2009 at 23:44 UTC | |
by Anonymous Monk on Jun 23, 2009 at 01:07 UTC | |
Re: Big-O Notation - What is it good for?
by jrtayloriv (Pilgrim) on Sep 29, 2009 at 04:24 UTC |