📘 Big O Notation Cheatsheet

Big O notation describes the time or space complexity of an algorithm in terms of how it scales with input size n.

📊 Common Complexities

Complexity	Name	Description	Example Use Cases
O(1)	Constant	Executes in the same time regardless of n	Accessing array element
O(log n)	Logarithmic	Cuts problem size in half each step	Binary search
O(n)	Linear	Grows proportionally with input size	Looping through an array
O(n log n)	Linearithmic	Slightly worse than linear	Merge sort, Quicksort (avg case)
O(n²)	Quadratic	Nested loops over the same input	Bubble sort, selection sort
O(2^n)	Exponential	Doubles with each addition to input	Recursive Fibonacci
O(n!)	Factorial	All permutations of input	Traveling salesman, brute-force

---

🧠 Quick Rules

• Drop constants → O(2n + 5) → O(n)
• Keep highest-order term → O(n² + n) → O(n²)
• Micro-optimizations < Algorithm design

---

🛠 Real-World Examples

Algorithm	Time Complexity
Array indexing	O(1)
Hash map lookup	O(1) (avg), O(n) (worst)
Linear search	O(n)
Binary search	O(log n)
Merge sort	O(n log n)
Bubble sort	O(n²)
Recursive Fibonacci	O(2^n)
Traveling salesman	O(n!)

---

📈 Growth Comparison

n	O(1)	O(log n)	O(n)	O(n log n)	O(n²)	O(2^n)	O(n!)
10	1	3.3	10	33	100	1024	3,628,800
100	1	6.6	100	660	10,000	1.27e30	~9e157
1,000	1	9.9	1,000	9,900	1,000,000	—	—

---

🚩 When to Worry

• Avoid O(n²) or worse for large datasets
• Prefer O(log n) or O(n) for scalability
• Watch out for hidden costs: API calls, recursion, memory

---

🧾 Notations Reference

• O → Upper bound (worst-case)
• Ω (Omega) → Lower bound (best-case)
• Θ (Theta) → Tight bound (average-case)

---

📌 Tip: Use tools like Big-O Cheat Sheet to compare algorithms visually.

📘 Big O Notation with JavaScript Code Examples

This guide provides common time complexities using Big O notation and example JavaScript functions. Perfect for interviews, notes, or GitHub Wiki use.

---

🟩 O(1) - Constant Time

The runtime does not increase with input size.

function getFirstItem(arr) {
  return arr[0];
}

🟩 O(log n) — Logarithmic Time (Binary Search)

The array size is halved each time (n → n/2 → n/4 → ...).

function binarySearch(arr, target) {
  let left = 0;               // O(1) - initialize left pointer
  let right = arr.length - 1; // O(1) - initialize right pointer

  // The loop runs while there's a search space to consider
  // Each iteration halves the remaining array → O(log n)
  while (left <= right) {
    const mid = Math.floor((left + right) / 2); // O(1) - find midpoint

    if (arr[mid] === target) return mid;        // O(1) - compare with target
    if (arr[mid] < target) left = mid + 1;      // O(1) - search in right half
    else right = mid - 1;                       // O(1) - search in left half
  }

  return -1; // O(1) - target not found
}

🟩 Merge Sort — O(n log n)

log n recursion levels (dividing array in half each time)

n work per level (merging all elements back together)

→ Total = O(n log n)

function mergeSort(arr) {
  if (arr.length <= 1) return arr; // Base case — O(1)

  const mid = Math.floor(arr.length / 2); // Divide — O(1)
  const left = mergeSort(arr.slice(0, mid));  // Recurse left — O(log n)
  const right = mergeSort(arr.slice(mid));    // Recurse right — O(log n)

  return merge(left, right); // Merge two halves — O(n)
}

function merge(left, right) {
  const result = []; // O(1)

  // While both arrays have elements
  while (left.length && right.length) {
    // Push the smaller element and remove it from its array — O(1)
    result.push(left[0] < right[0] ? left.shift() : right.shift());
  }

  // Concatenate leftover elements — O(n)
  return result.concat(left, right);
}

🟩 O(2ⁿ) — Exponential Time

he recursion tree grows exponentially — each level doubles the number of calls

function fibonacci(n) {
  // Each call generates two more calls — exponential growth
  if (n <= 1) return n;

  return fibonacci(n - 1) + fibonacci(n - 2); // O(2ⁿ)
}

🟩O(n!) — Factorial Time

For a string of length n, we generate n! permutations.

function getPermutations(str) {
  // Base case: a single permutation
  if (str.length <= 1) return [str];

  const result = [];

  // Generate all permutations
  for (let i = 0; i < str.length; i++) {
    const char = str[i];
    const remaining = str.slice(0, i) + str.slice(i + 1);
    const subPerms = getPermutations(remaining); // O((n-1)!)

    for (const perm of subPerms) {
      result.push(char + perm); // Combine permutations
    }
  }

  return result; // Total permutations = n!
}

🟩 O(n²) — Quadratic Time

For each element, we loop over the entire array again.

function printAllPairs(arr) {
  // Nested loop → O(n²)
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      console.log(arr[i], arr[j]); // O(1) per pair
    }
  }
}

🟩 O(n) — Linear Time

The function processes every element exactly once

function printAllItems(arr) {
  // Visit each element once → O(n)
  for (let i = 0; i < arr.length; i++) {
    console.log(arr[i]); // O(1) per item
  }
}