DEV Community

Imamuzzaki Abu Salam
Imamuzzaki Abu Salam

Posted on • Originally published at blog.imam.dev

5

Big O Notation in JavaScript

Big O Notation, collectively called Bachmann-Landau notation or asymptotic notation, is a way to describe the performance of an algorithm. It is used to describe the worst-case scenario of an algorithm. It is used to compare the performance of different algorithms. It describes the implementation of an algorithm in terms of the input size.

Big O notation characterizes functions according to their growth rates: tasks with the same growth rate are considered to be of the same order. It is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is used to classify algorithms according to how their run time or space requirements grow as the input size grows. The letter O is used because the growth rate of a function is also called its order.

Iteration

For loop

for (let i = 0; i < n; i++) {
  console.log(i)
}
Enter fullscreen mode Exit fullscreen mode

The above code will run n times. The time complexity of this code is O(n).

While loop

let i = 0
while (i < n) {
  console.log(i)
  i++
}
Enter fullscreen mode Exit fullscreen mode

The above code will run n times. The time complexity of this code is O(n).

Do while loop

let i = 0
do {
  console.log(i)
  i++
} while (i < n)
Enter fullscreen mode Exit fullscreen mode

The above code will run n times. The time complexity of this code is O(n).

Recursion

Factorial

function factorial(n) {
  if (n === 0) {
    return 1
  }
  return n * factorial(n - 1)
}
Enter fullscreen mode Exit fullscreen mode

The above code will run n times. The time complexity of this code is O(n).

Fibonacci

function fibonacci(n) {
  if (n <= 1) {
    return n
  }
  return fibonacci(n - 1) + fibonacci(n - 2)
}
Enter fullscreen mode Exit fullscreen mode

The above code will run n times. The time complexity of this code is O(n).

Searching

Linear search

function linearSearch(arr, value) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === value) {
      return i
    }
  }
  return -1
}
Enter fullscreen mode Exit fullscreen mode

The above code will run n times. The time complexity of this code is O(n).

Binary search

function binarySearch(arr, value) {
  let start = 0
  let end = arr.length - 1
  let middle = Math.floor((start + end) / 2)
  while (arr[middle] !== value && start <= end) {
    if (value < arr[middle]) {
      end = middle - 1
    } else {
      start = middle + 1
    }
    middle = Math.floor((start + end) / 2)
  }
  if (arr[middle] === value) {
    return middle
  }
  return -1
}
Enter fullscreen mode Exit fullscreen mode

The above code will run log(n) times. The time complexity of this code is O(log(n)).

Sorting

Bubble sort

function bubbleSort(arr) {
  for (let i = arr.length; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }
  return arr
}
Enter fullscreen mode Exit fullscreen mode

The above code will run n^2 times. The time complexity of this code is O(n^2).

Selection sort

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let lowest = i
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[lowest]) {
        lowest = j
      }
    }
    if (i !== lowest) {
      let temp = arr[i]
      arr[i] = arr[lowest]
      arr[lowest] = temp
    }
  }
  return arr
}
Enter fullscreen mode Exit fullscreen mode

The above code will run n^2 times. The time complexity of this code is O(n^2).

Insertion sort

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let currentVal = arr[i]
    for (var j = i - 1; j >= 0 && arr[j] > currentVal; j--) {
      arr[j + 1] = arr[j]
    }
    arr[j + 1] = currentVal
  }
  return arr
}
Enter fullscreen mode Exit fullscreen mode

The above code will run n^2 times. The time complexity of this code is O(n^2).

Merge sort

function mergeSort(arr) {
  if (arr.length <= 1) return arr
  let mid = Math.floor(arr.length / 2)
  let left = mergeSort(arr.slice(0, mid))
  let right = mergeSort(arr.slice(mid))
  return merge(left, right)
}

function merge(left, right) {
  let results = []
  let i = 0
  let j = 0
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      results.push(left[i])
      i++
    } else {
      results.push(right[j])
      j++
    }
  }
  while (i < left.length) {
    results.push(left[i])
    i++
  }
  while (j < right.length) {
    results.push(right[j])
    j++
  }
  return results
}
Enter fullscreen mode Exit fullscreen mode

The above code will run n log(n) times. The time complexity of this code is O(n log(n)).

Quick sort

function pivot(arr, start = 0, end = arr.length + 1) {
  let pivot = arr[start]
  let swapIdx = start
  function swap(array, i, j) {
    let temp = array[i]
    array[i] = array[j]
    array[j] = temp
  }
  for (let i = start + 1; i < arr.length; i++) {
    if (pivot > arr[i]) {
      swapIdx++
      swap(arr, swapIdx, i)
    }
  }
  swap(arr, start, swapIdx)
  return swapIdx
}

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(arr, left, right)
    quickSort(arr, left, pivotIndex - 1)
    quickSort(arr, pivotIndex + 1, right)
  }
  return arr
}
Enter fullscreen mode Exit fullscreen mode

The above code will run n log(n) times. The time complexity of this code is O(n log(n)).

Tips for Big O

  • Arithmetic operations are constant
  • Variable assignment is constant
  • Accessing elements in an array (by index) or object (by key) is constant
  • In a loop, the complexity is the length of the loop times the complexity of whatever happens inside of the loop

Resources

Neon image

Build better on Postgres with AI-Assisted Development Practices

Compare top AI coding tools like Cursor and Windsurf with Neon's database integration. Generate synthetic data and manage databases with natural language.

Read more →

Top comments (0)

Neon image

Next.js applications: Set up a Neon project in seconds

If you're starting a new project, Neon has got your databases covered. No credit cards. No trials. No getting in your way.

Get started →

👋 Kindness is contagious

Explore a trove of insights in this engaging article, celebrated within our welcoming DEV Community. Developers from every background are invited to join and enhance our shared wisdom.

A genuine "thank you" can truly uplift someone’s day. Feel free to express your gratitude in the comments below!

On DEV, our collective exchange of knowledge lightens the road ahead and strengthens our community bonds. Found something valuable here? A small thank you to the author can make a big difference.

Okay