Big O Notation helps us determine how complex an operation is. It's of particular interest to the field of Computer Science. So for all you CS geeks out there here's a recap on the subject!

When you start delving into algorithms and data structures you quickly come across Big O Notation. It tells us how long an operation will take to run, as the size of the data set increases.

It's also a measure of complexity. The simple fact is that if something takes longer to run it is obviously more complex... logical eh? :)

Here's a list of the more common Big O Notations from fastest (best) to slowest (worst).

Notation | Description |
---|---|

O(1) | Constant: operations occur at the same speed no matter the size of the data set.
ie. doing a null check |

O(log n) | Logarithmic: operations take slightly longer as the size of the data set increases in orders of magnitude. Very close to O(1).
ie. finding an item in a sorted data set using a binary search |

O(n) | Linear: operations take longer in direct proportion to the size of the data set.
ie. adding up all the values in data set |

O(n log n) | Linearithmic: as the data set doubles in size, operations take longer by an increasing multiplier of one.
ie. a quick sort |

O(n^{2}) |
Quadratic: as the data set doubles in size, operations take four times longer.
ie. two nested loops over a data set |

O(2^{n}) |
Exponential: for every new element added to the data set operations take twice as long.
ie. brute force attacking a password |

O(n!) | Factorial: operations take n! times longer in direct proportion to the size of the data set.
ie. calculating fibonacci numbers recursively |

They say a picture is worth a thousand words so this should help greatly with your understanding of the above :)

The key take away here is that if you are working with large data sets you need to be very careful when selecting the data structure and/or algorithm you use.

I'm going to be starting a new series on Data Structures soon which will reference these Big O notations. That'll help show the real world application of these theoretical concepts.

Until then... happy coding!