Big O Notation

The speed and memory usage of an algorithm aren’t necessarily fixed; they might change depending on the input. So how do we express the performance of an algorithm then?

Enter Big O Notation, a powerful tool that allows us to generalize the space-time complexity of an algorithm as a function of its input size.

Let’s say we have an array of n length

$$ a = […] $$

And the following functions

$$ f_1(a) = 1 + a[0] $$

Simply returns the first element of array plus one

$$ f_2(a) = sum(a) $$

Return the sum of all elements in array

$$ f_3(a) = pair(a) $$

Each possible pair combination

All of those algorithms take an array.

const sum = arr => arr.reduce((acc, el) => acc + el, 0)
const pair = arr => 
  arr.map(mainEl => arr.map(secondEl => [mainEl, secondEl]))

const arrayWithLengh = length => Array.from({length}, (v, k) => k+1)


const a = arrayWithLengh(10)
const a100Elements =  arrayWithLengh(100)
const a1000Elements = arrayWithLengh(1000)

const f1 = (x) => 1 + x[0]
const f2 = (x) => sum(x) 
const f3 = (x) => pair(x)

// Computed time For 1 Element
f1(a) // ~0.021ms (for 1 element)
f2(a) // ~0.046ms (for 1 element)
f3(a) // ~0.065ms (for 1 element)

// Computed time For 10 Elements
f1(a) // ~0.027ms (for 10 elements)
f2(a) // ~0.059ms (for 10 elements)
f3(a) // ~0.116ms (for 10 elements)

// Computed time For 100 Elements
f1(a100Elements) // ~0.021ms (for 100 elements)
f2(a100Elements) // ~0.071ms (for 100 elements)
f3(a100Elements) // ~3.644ms (for 100 elements)

// Computed time For 1000 Elements
f1(a1000Elements) // ~0.020ms (for 1000 elements)
f2(a1000Elements) // ~0.263ms (for 1000 elements)
f3(a1000Elements) // ~96.810ms (for 1000 elements)

You can see that the speed of each algorithm is directly related to the length of the array. Big O notation help us understand and compare the complexity of each algorithm.

$$ f_1(a) = 1 + a[0] $$

Time Complexity: **O(1)**


          **Constant**

$$ f_2(a) = sum(a) $$

Time Complexity: **O(N)**


              **Linear**

$$ f_3(a) = pair(a) $$

Time Complexity: O(N²)

          **Quadratic**

Asymptotic Analyses

An example of What is Asymptotic Analyses? is a function f4 that contains all other functions

$$ f_4(a)= f_1(a) + f_2(a) + f_3(a) $$

This means that f4 have the complexity of

$$ O(1) + O(n) + O(n^2) ∴ O(n^2 + n + 1) $$

But notice how n and 1 is irrelevant when compared with n², so in this case we just say O(n²)

Most Used Notations

$$ O(1) \ \scriptsize \color{gray}Constant $$

$$ O(log\space n) \ \scriptsize \color{gray} Logaritimic $$

$$ O(n) \ \scriptsize \color{gray} Linear $$

$$ O(n * log\space n) \ \scriptsize \color{gray} Linearithimic $$

$$ O(n^2), O(n^3), O(n^4) \ \scriptsize \color{gray} Quadratic, Cubic, Polynomial $$

$$ O(2^n) \ \scriptsize \color{gray} Exponential $$

$$ O(n!) \ \scriptsize \color{gray} Factorial $$

🔥 Big O Notation always refer to the worst case scenario

Few Examples

O(25) → O(1)

O(2n) → O(n)

O(n² + 2n) → O(n²)

O(n³ + log(n) + 3) → O(n³)

O(n + m) → O(n + m)

O(2n + m) → O(n + m)

The most common Big O Notations are:

O(1) → Constant | Accessing a memory address

O(log n) → Logarithmic | Binary Search

O(n) → Linear | Iterating an Array

O(n log n) → Linearithimic | Iterating an Array

O(n²) → Quadratic | Nested Iterations

O(2^n) → Exponential | Nested Iterations

O(n!) → Factorial | Generate all permutations of a list

Time Complexity

A measure of how fast an algorithm runs, time complexity is a central concept in the field of algorithms. It’s expressed by using Big O notation.

Space Complexity

A measure of how much auxiliary memory an algorithm takes up, space complexity is a central concept in the field of algorithms and it’s also expressed using Big O notation

Flash Cards