Big O Notation

What is Big O Notation?

Simplified analysis of an algorithm's efficiency in worst case scenario (very large input size).

Formula

O(n)

• O: represents the function or algorithm that is being evaluated... "Big O"
• n: represents the number of elements/input

Big O: Order of Complexity

	Notation	Name	short	Description
🤩	O(1)	Constant	speed isn't determined by input size	Always takes the same amount of time regardless of input size
😁	O(log n)	Logarithmic	10x data means 2x more time	Amount of work is divided by 2 after every loop iteration (binary search)
🙂	O(n)	Linear	10x more data means 10x more time	How long it takes to run is directly based on how big N is (for loops)
😒	O(n·log(n))	Log-linear or Linearithmic	10x more data means about 20x more time	nested loop where the inner loop runs in log n time. (quicksort, mergesort & heapsort)
😬	O(n^2)	Quadratic	10x more data means 100x more time	you have a loop that for each element then loops over every element in nested loop
😳	O(2^n)	Exponential

General Rules

1. Certain terms dominate others, drop lower order terms

O(1) < O(log n) < O(n) < O(n·log(n)) < O(n²) < O(2ⁿ) < O(n!)

2. Ignore constants

5n -> n -> O(n)

Examples

T(n) = 17n⁴ + 3n³ + 4n + 8

1. O(n⁴) dominates over O(n³) O(n) O(1)

T(n) = 17n⁴

2. Ignore constants

T(n) = O(n⁴)

Constant Runtime | O(1) | O of 1

As the input size increases, the number of operations that we perform never changes.

// Big O Notation: O(1)
function log(array) {
  console.log(array[0]);
  console.log(array[1]);
}

Logarithmic Runtime | O(log n) | O of log n

With every operation performed we cut the input in half.

// Big O Notation: O(log n)
function binarySearch(array, key) {
  var low = 0;
  var high = array.length - 1;
  var mid;
  var element;

  while (low <= high) {
    mid = Math.floor((low + high) / 2, 10);
    element = array[mid];
    if (element < key) {
      low = mid + 1;
    } else if (element > key) {
      high = mid - 1;
    } else {
      return mid;
    }
    return -1;
  }
}

Linear Runtime | O(n) | O of n

• The runtime is proportional to the input size.
• As the input increases so does the runtime.
• Each time we add to input we add to how many times we need to execute the function.

// Big O Notation: O(n)
function logAll(array) {
  for (var i = 0; i < array.length; i++) {
    console.log(array[i]);
  }
}

Quadratic Runtime | O(n^2) | O of n squared

• Iterates through the entire array and for every element it goes through the entire array again.

// Big O Notation: O(n^2)
function addAndLog(array) {
  for (var i = 0; i < array.length; i++) {
    for (var j = o; j < array.length; j++) {
      console.log(array[i] + array[j]);
    }
  }
}

Exponential Runtime | O(2^n) | O of 2 raised to the n-th power

• Runtime grows exponentially based on input size.

// Big O Notation: O(2^n)
function fibonacci(num) {
  if (num <= 1) return 1;

  return fibonacci(num - 1) + fibonacci(num - 2);
}