Big-O for Eight Year Olds?

A lot of these are easy to demonstrate with something non-programming, like shuffling cards.

Sorting a deck of cards by going through the whole deck to find the ace of spades, then going through the whole deck to find the 2 of spades, and so on would be worst case n^2, if the deck was already sorted backwards. You looked at all 52 cards 52 times.

In general the really bad algorithms aren't necessarily intentional, they're commonly a misuse of something else, like calling a method that is linear inside some other method that repeats over the same set linearly.

No, an O(n) algorithm does not mean it will perform an operation on each element. Big-O notation gives you a way to talk about the "speed" of you algorithm independent of your actual machine.

O(n) means that the time your algorithm will take grows linearly as your input increase. O(n^2) means that the time your algorithm takes grows as the square of your input. And so forth.

One thing that hasn't been touched on yet for some reason:

When you see algorithms with things like O(2^n) or O(n^3) or other nasty values it often means you're going to have to accept an imperfect answer to your problem in order to get acceptable performance.

Correct solutions that blow up like this are common when dealing with optimization problems. A nearly-correct answer delivered in a reasonable timeframe is better than a correct answer delivered long after the machine has decayed to dust.

Consider chess: I don't know exactly what the correct solution is considered to be but it's probably something like O(n^50) or even worse. It is theoretically impossible for any computer to actually calculate the correct answer--even if you use every particle in the universe as a computing element performing an operation in the minimum possible time for the life of the universe you still have a lot of zeros left. (Whether a quantum computer can solve it is another matter.)

The "Intuitition" behind Big-O

Imagine a "competition" between two functions over x, as x approaches infinity: f(x) and g(x).

Now, if from some point on (some x) one function always has a higher value then the other, then let's call this function "faster" than the other.

So, for example, if for every x > 100 you see that f(x) > g(x), then f(x) is "faster" than g(x).

In this case we would say g(x) = O(f(x)). f(x) poses a sort of "speed limit" of sorts for g(x), since eventually it passes it and leaves it behind for good.

This isn't exactly the definition of big-O notation, which also states that f(x) only has to be larger than C*g(x) for some constant C (which is just another way of saying that you can't help g(x) win the competition by multiplying it by a constant factor - f(x) will always win in the end). The formal definition also uses absolute values. But I hope I managed to make it intuitive.

Remember the fable of the tortoise and the hare (turtle and rabbit)?

Over the long run, the tortoise wins, but over the short run the hare wins.

That's like O(logN) (tortoise) vs. O(N) (hare).

If two methods differ in their big-O, then there is a level of N at which one of them will win, but big-O says nothing about how big that N is.