Big Oh Notation

Big O notation is a cornerstone in analyzing algorithms. Not only does your code need to work, it also needs to work at max efficiency related to time and space based on a given input.

How does runtime change as n gets bigger?

Assume in the following scenario that you have a USB flash drive of 10,000 pictures. To send all 10,000 pictures from your house in California to your friend’s house in Taiwan over the internet (electronically) is dependent on factors such as internet speed and bandwidth, but primarily based on the size of your input n (n = 10,000 JPGs). 1 JPG can be sent almost immediately, but 10,000 JPGs will take 10,000 times the speed of 1 JPG. The electronic runtime of this process is linear with n; as n increases, so does runtime. So what happens n = 100,000? n = 1,000,000? At some point, it could just be faster to place the USB flash drive on a nonstop flight from LAX to TPE, in which case the runtime would be constant; regardless of 100,000 or 10,000,000 files, the total transfer time will be flight time.

Big O analysis:

  • is a simplified way to analyze an algorithm’s basic efficiency

Let’s take a look at a few examples in psuedocode:

O(1) — Constant

method FirstElement (array)
puts array[0]

Here we have a method FirstElement that takes an input Array and puts the first element of the array. The runtime of this method is O(1) — regardless of size n, it will only print the first element of the array (total number of steps do not change as n increases).

O(n) — Linear

method LoopElement (array)
for i = 0; i < array.length; i++
puts array[i]
end

This method LoopElement also takes an array of size n as its input, but it now loops through each item in the array and print each item of the array. Now, as n increases, the number of prints increases linearly.

O(n²) — Quadratic (multiplying runtimes)

method NestedLoop (array)
for i = 0; i < array.length; i++
for j = 0; j < array.length; j++
puts array[i] , array[j]
end

Here we have a nested loop; the outer loop loops through all elements, then the inner loop does the same, and outputs two array elements. If the size of array n = 100, there will be 10,000 executions of puts. As the number of n elements increases, the number of steps will increase exponentially. This is one of the slowest runtimes. Each loop is O(n) time, so O(n) * O(n) = O(n²).

O(n) — Linear (adding runtimes)

method LoopElement (array)
for i = 0; i < array.length; i++
puts array[i]
end
for i = 0; i < array.length; i++
puts array[i]
end

Here we have two loops run sequentially (not nested). When the first loop is completed, the second loop begins. Each loop has a runtime of O(n), so the two loops together have a runtime of O(2n). But remember, since we drop the constants, this method of two loops has a total runtime of O(n).

O(log n)

This runtime occurs in algorithms in which the number of elements n is halved each time the algorithm is called. For example, in binary search, you are looking for an example X in an N-element sorted array:

  1. Start with N-element array to search

This continues until element X is found. The runtime grows at a slower rate compared to increase in n.

n * 1/2 * 1/2 * 1/2 .... = 1
1 * 2 * 2 * 2.... = n

Both scenarios above are situations with O(log n) time.

O(n log n)

A good example of an algorithm with O(n log n) runtime is Merge Sort. Merge Sort can take an input array of n numbers, unsorted, and return an output array of n numbers, sorted in increasing order. How?

  1. Recursively sort first half of the input array

The runtime of the recursive sort is O(log n) since after each recursion, the input is halved and the runtime of the merge is O(n), so the total runtime is O(log n) * O(n) = O(n log n).

Why is Big O analysis important?

Big O analysis is a good way to evaluate an algorithm’s efficiency at a high level and provide an algorithm’s expected behavior in relation to input sizes. Understanding Big O allows you to look at a function and determine what kind of runtime to expect and if you should try to improve it (e.g. if your algorithm has a runtime of O(n²), you should definitely try to improve it). It is also a topic that comes up frequently in technical interviews, so it’s a must-know for those going through that process.

--

--

wife. product @airbnb. traveler. DIY-er at @imperfect.thread

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store