Working With Big O Notation
While Big O notation can sound lofty and engender a feeling of foreboding, it is actually quite simple tool in estimating the efficiency of code and algorithms. Big O’s importance is related to the way that it achieves its estimations. Big O does not strictly monitor the speed it takes a line of code to run. Speed is dependent on processing power and other variables that are not reliable and can detract from the fidelity of analysis. Big O Notation instead tests the amount of steps a code takes to execute as the algorithm’s input grows in size towards infinity.
Big O Notation is an example of asymptotic notation. This is to say Big O Notation tracks the upper bound of input size as it grows in order to give estimations of time complexity at their worst case. While Big O tests for the worst case time complexity any operations that do not significantly impact the growth-rate in time complexity are omitted. For example: O(n + 5) is simplified to O(n) because the five constant operations bear little to no impact on the data as our input n grows towards infinity.
O(1) Constant Time:
const multiplyMil = function(num){
return num * 1000000}const retrieveIndex1 = array => array[1]
retrieveIndex1([1,2,3,4])
Constant Time is distinguished by the fact that no matter the input into a problem it has constant set of processes that it will execute. It may be a 1000 processes but the processes do not scale alongside the size of the input thus it is constant.
O(logn) Logarithmic Time:
The textbook example of Logarithmic time is a binary search tree where tree traversal is determined by a value being less or more than the value at the current node. A balanced binary search tree should yield close to constant time and as n reaches higher and higher inputs the likelihood of that balance increases. A logarithm in simple terms is the inverse of exponential growth for example log base 2 of 1024 = 10. 10 is logarithmically smaller than 1024 so if you take an operation that would normally take 1024 seconds and get it to taking 10 seconds you have a finely tuned algorithm.
O(n) Linear Time:
const addElement = (array) => for(let element of array){
array.push(element)}The simplest way to locate linear time within a algorithm is if the input n is iterable and in order to execute the operations you must cycle through some number of n, you are dealing with linear time. Linear time is where we begin to deal with less than ideal time complexity. While some problems require the implementation solutions that are O(n) or worse, since these times grow proportionally with the input they will not be friendly to large data sets and databases.
On the other hand, it is important to remember that Big O Notation tests solutions not problems. While there may be a function that takes a parameter n that is an array with only five data points, we cannot say there are 5 constant operations here because those operations scale with the input thus it has a linear time complexity.
O(nlog(n) commonly relate to sorting algorithms. While each node is hit multiple times during the functions processes it does not scale like quadratic time so it is a more preferable time complexity.
O(n²) Quadratic time:
function do(array){
for(let i = 0; i < array.length; i++){
for(let j = 0; j < array[i].length; j++){
console.log(array[i][j])}}}
This time complexity is commonly seen with loops within loops. The more nested loops the code contains the higher the power n must be raised to. This time complexity is to be avoided wherever possible. How does O(n²) differs from the code below?
function dd(array){
for(let i = 0; i < array.length; i++){
console.log(array[i])}
for(let j = 0; j < array.length; j++){
array[j]++
}While there are two loops within the code above they are not nested within each other so the time complexity of the dd function is O(2n). Constants are dropped so the time complexity is simplified as O(n).
O(n!) Factorial Time:
N factorial comes into play when there is a prompt to find all the permutations of a collection n. Permutations by definition have a factorial time complexity.
For me, when learning a new topic in computer science I have to relate it to a personal experience no matter how belabored the analogy ends up being. The more the topic skews towards math and science, the greater necessity for me to dumb down it down in order to understand it’s distinct parts. To tackle ideas related to Big O notation let’s take some data points — say, the name of train stops.
redLineStops = ["95th", "87th", "79th", "69th", "63rd", "55th", "47th", "sox-35th", "cermak-chinatown"];I find trains stops to be an easy way to think about node traversal because when taking a commuter train, a passenger is literally stopping at regular intervals to wait while the process of emptying and entering passengers before the train starts up again. Also this analogy doevetails nicely with Big O Notation because while you know your stop. the worst case scenario is that you’ll be on the train the entirety of the route.
In this way: taking a commuter train can be expressed in linear time. The more stops the train line has the more instances of loading and unloading passengers will occur. For example:
const commuter = array => {
const trainStop = () => {console.log('stop')}
const trainResume = () => {console.log('the doors are closing')
for(let stops of array){
trainStop();
trainResume()}}
commuter(redlineStops)The ubiquity of ridesharing apps has shown how preferential constant time is. If you put in an address, going to that address will be constant no matter what. While the amount of time it takes for you to get to that address may vary the position and processes do not increase related to that output. For example:
const rideshare = (address) => {
console.log(`arrived at ${address}`)
}Finally let’s give an example of quadratic time with our strained analogy here. Say we have an array of train lines that a tourist needs to use to get to a certain location. If the tourist does not know which train line to take they must take all of the train lines and stop at all of the stops to figure out if they are in the correct location. As the amount of train lines and train routes grow the possibilities of that unknown grow exponentially. It is apparent that the tourist needs to stop and rethink their plan of engagement.
const elStops = [blueLineStops, redLineStops, yellowLineStops, purpleLineStops, brownLineStops, pinkLineStops]
const tourist = array => {or(let i = 0; i < array.length; i++){for(let j= 0; j < array[i].length; j++){return array[i][j] === 'fullerton'}}}tourist(elStops)
That’s the basics of how Big O is quantified. The important bit is using it to think about how many steps your function is taking based on its data input and think about how to increase its efficiency.
Resources:
Take Up Code Podcast: ‘Big-O Notation. Take It To The Limit’ — Wahid Tanner
Take Up Code Podcast:
