What's an easy way to understand Big-O notation?

Question

I don't get this Big-O notation stuff (I was never good with math). Is there like a quick rule of thumb to understand how to choose an algorithm based on just its Big-O notation? For example, what would be considered slow and fast in Big-O notation?

Answer 1

This is not entirely mathematically correct, but here goes:

O(1) < O(x) < O(xlogx) < O(x^2) < ... < O (x^n)

That reads algorithm of speed Big O of 1 is always faster than algorithm of speed Big O of x and algorithm of speed Big O of x is always faster than algorithm of speed Big O of xlogx and so on.

The variable x stands for input size; that could be size of array, depth of a tree, population of a tree, length of a string, whatever, but it is some quantity of size not the value of input itself, a quick way of understanding O() is the extra steps that an algorithm has to go through for a growth in input size:

if no extra - it is O(1) speed
if growth and extra steps are proportionate - O(x)
if growth:extra step ratio is xlogx - it is O(xlogx)
...