If you’re like me you may have forgotten all about Big O Notation. This post aims to serve as a refresher for myself and hopefully others.

What is Big O Notation?

Big O notation is used to measure the efficiency of an algorithm. It does not measure speed rather it measures the number of operations in terms of its growth. It helps you understand how efficient (or inefficent) some an algorithm performs. This is good to know for both your own code as well as any dependencies you use.

What exactly does Big O Notation represent?

Big O notation describes the worst case for an algorithm. We aren’t interested in whether or not you found an item on the first or second try. It’s all about the worst case. If you need to search 8 unsorted boxes for a unique value, in the worst case you would need to so search all 8 boxes, which is O(n) where n is total number of boxes. In mathematical terms worst case is synonomous with upper bound.

Constant Time

I find the easiest Big O representation to understand is something know as constant time. The most common example of this is a hash lookup. Given a key, you only need to look up one field thus its known as contant time: O(1)

Linear Time

Looking up an element by searching through all the elements exactly once is known as linear time. Which is represented as: O(n)

Log Time

If you have a sorted list of elements, you can use a binary search algorithm which is: O(logn)

Log Review

When taking about Big O notation, log is usually implicitly referring to log2

You can think of logs as the reverse of exponents. What do we have to raise 2 by get the 2nd number?

log2 32 = 5
log2 8 = 2

Common Big O Notation Times

Notation Example Term
O(1) hash lookup constant time
O(log n) binary search log time
O(n) simple search linear time
O(n * log n) quick sort  
O(n2) selection  
O(n!) recursive factorial time

Remember these:

20 1
21 2
22 4
23 8
24 16
25 32
26 64
27 128
28 256
29 512
210 1024
211 2048
212 4096