Intro to Big O Notation

In preparation for technical interviews, this week I began to explore Big O Notation.

What is Big O? According to https://web.mit.edu/, Big O, sometimes also referred to as asymptotic analysis, is a “symbolism used in complexity theory, computer science, and mathematics to describe the asymptotic behavior of functions.” It measures the runtime complexity of our algorithms, in other words, the efficiency or performance and scalability of our functions with accordance to their input value.

As an introduction to Big O, today I’ll be discussing the following runtime complexities:

• Linear
• Quadratic
• Logarithmic

Find max element in an unsorted array:
function findMax(array) {
  let max = 0;
  for (let i = 0; i < array.length; i++){
    if (array[i] > max) {
      let max = array[i]
    }
   }
  return max;
}

LINEAR The above code runs in linear time or O(n). What does this mean? The amount of time and space it takes our program to run this code, increases linearly in direct correlation to the size of the input value. In other words, the longer our array the more costly our runtime. This may not have much of an impact when working with smaller arrays but imagine having to iterate through each and every element of an array made up of millions of records to run your function?! Now that would be expensive! $$$

Sorting an array with bubble sort:
function bubbleSort(array) {
 for (let i= 0; i < array.length; i++) {
   for (let j = 1; j < array.length - i; j++) {
     if (array[j] < array[j - 1]){
       //swap
       let temp = array[j];
       array[j] = array[j-1];
       array[j - 1] = temp;
       sorted = false;
     }
   }
 }
 return array;
}

QUADRATIC Herein we’ve introduced an additional layer of complexity with a nested loop in our function. Keeping the runtime O(n) (discussed above) for the first loop, we now must factor in or add the cost of running the inner loop, which also happens to be O(n). What is the cost of running O(n) n times → O(n²)!

Finding element in sorted array with binary search:
function findInSorted (array, value){
  let firstIndex  = 0,
  let lastIndex   = items.length - 1,
  let middleIndex = Math.floor((lastIndex + firstIndex)/2);
while(array[middleIndex] != value && firstIndex < lastIndex)
    {
      if (value < items[middleIndex])
        {
            lastIndex = middleIndex - 1;
        } 
      else if (value > items[middleIndex])
        {
            firstIndex = middleIndex + 1;
        }
      middleIndex = Math.floor((lastIndex + firstIndex)/2);
      return (items[middleIndex] != value) ? -1 : middleIndex;
}

LOGARITHMIC Logarithmic time, depicted as O(log n), often describes code written to perform binary searches. It is the most efficient and scalable of the three as it cuts or reduces work in half at every stage.

These are just a few of the many Big O runtime complexities. For a neat cheat sheet visit: https://www.bigocheatsheet.com/.