Big O Notation Explained: The Complete Guide Every Developer Must Know

// O(2n) simplifies to O(n)
// O(n + 500) simplifies to O(n)
// O(3n² + 50n + 1000) simplifies to O(n²)

// Rule: keep the dominant term, drop everything else
// As n → ∞, constants become irrelevant
// 1000n vs n²: at n=1001, n² wins forever

// Same time regardless of input size
function getFirst(arr) { return arr[0]; } // O(1)
function isEven(n) { return n % 2 === 0; } // O(1)
const map = new Map(); map.get('key'); // O(1) average
const set = new Set(); set.has(42); // O(1) average

// Hash tables, array access by index = O(1)
// Stack push/pop, queue enqueue/dequeue = O(1)

// Input is halved each iteration — classic binary search
function binarySearch(arr, target) {
 let lo = 0, hi = arr.length - 1;
 while (lo <= hi) {
 const mid = (lo + hi) >> 1;
 if (arr[mid] === target) return mid;
 arr[mid] < target ? lo = mid + 1 : hi = mid - 1;
 }
 return -1;
}
// n=1,000,000 → only 20 iterations (log₂ 1,000,000 ≈ 20)
// Balanced BST operations, heap insert/extract = O(log n)

// Touch every element once
function sum(arr) {
 let total = 0;
 for (const x of arr) total += x; // n iterations
 return total;
}
// Linear search, array traversal, single-pass algorithms
// If you have TWO separate loops (not nested): still O(n)
function twoLoops(arr) {
 for (const x of arr) doA(x); // O(n)
 for (const x of arr) doB(x); // O(n)
 // Total: O(2n) = O(n) — not O(n²)!
}

// Optimal comparison-based sorting
// Merge sort: divide in half O(log n), merge each half O(n)
// Result: O(n log n) — the theoretical minimum for comparison sort

// JavaScript built-in sort: O(n log n)
[5,3,1,4,2].sort((a,b) => a-b);

// Merge sort implementation:
function mergeSort(arr) {
 if (arr.length <= 1) return arr;
 const mid = arr.length >> 1;
 const L = mergeSort(arr.slice(0, mid));
 const R = mergeSort(arr.slice(mid));
 return merge(L, R); // O(n) merge
} // T(n) = 2T(n/2) + O(n) = O(n log n) by Master Theorem

// Nested loops over same input = n² operations
function bubbleSort(arr) {
 for (let i = 0; i < arr.length; i++) { // n
 for (let j = 0; j < arr.length - i; j++) { // n
 if (arr[j] > arr[j+1]) [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
 }
 }
} // O(n²) — avoid for large inputs

// O(n²) warning signs:
// - Nested loop over same array
// - Checking all pairs: for i, for j where j > i
// - N+1 query pattern in databases

// O(2ⁿ): naive recursion without memoization
function fib(n) {
 if (n <= 1) return n;
 return fib(n-1) + fib(n-2); // Each call spawns 2 more
} // Calls grow as 2ⁿ — fib(50) = 2⁵⁰ calls!

// Fix: memoization → O(n)
const memo = new Map();
function fibMemo(n) {
 if (n <= 1) return n;
 if (memo.has(n)) return memo.get(n);
 const result = fibMemo(n-1) + fibMemo(n-2);
 memo.set(n, result);
 return result;
}

// O(n!): generating all permutations — only feasible for n < 12
// Traveling Salesman brute force, naive scheduling

// Space complexity measures additional memory allocated

// O(1) space: in-place, no extra structure
function reverseInPlace(arr) {
 let l=0, r=arr.length-1;
 while(lhi) return -1;
 const mid=(lo+hi)>>1;
 if(arr[mid]===t) return mid;
 return arr[mid]