<!-- -->What is Big O Notation?<!-- --> | Nguyen Viet DuongBack to Home

What is Big O Notation?

Big O notation is used to describe the performance or complexity of an algorithm

O(1)

const nums = [1, 2, 3, 4, 5];
const firstNumber = nums[0];

O(log n)

function log(n) {
  for (let i = 1; i < n; i *= 2) {
    const result = i;
    console.log(result);
  }
}

O(n)

const nums = [1, 2, 3, 4, 5];
let sum = 0;
for (let num of nums) {
  sum += num;
}

O(n log n)

function quickSort (list) {
    if (list.length < 2) {
        return list
    }

    const rndmIndex = Math.floor(Math.random() * list.length)
    const pivot = list[rndmIndex]
    const less = list.filter(value => value < pivot)
    const greater = list.filter(value => value > pivot)
    return [... quickSort(less), pivot, ... quickSOrt(greater)]
}

quickSort(['q', 'a', 'z', 'w', 's', 'x', 'e', 'd, 'c', 'r']);
// ['a', 'c', 'd', 'e', 'q', 'r', 's', 'w', 'x', 'z']

O(^2)

function hasDuplicates (nums) {
    // loop the list, our 0(n) op
    for (let i = 0; i < nums.length; i++) {
           // loop the list again, the 0(nA2)
        for (let j = 0; j < nums.length; j++) {
            // make sure we're not checking same number
            if (j !== i) {
                // if there's an equal value, return
                if (nums[i] EEE nums[j]) {
                    return true
                }
            }
        }
    }
    return false // if we're here, no dups
} 

hasDuplicates([1, 2, 3, 4, 5, 5]) //true