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).
|Constant: operations occur at the same speed no matter the size of the data set.
ie. doing a null check
|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
|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
|Quadratic: as the data set doubles in size, operations take four times longer.
ie. two nested loops over a data set
|Exponential: for every new element added to the data set operations take twice as long.
ie. brute force attacking a password
|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!