Big O Notation Examples in JavaScript

O(1) — Constant Time

Operation takes the same time regardless of input size (e.g., array index access).

        function getFirstElement(arr) {
            return arr[0]; // Always 1 operation
        }
    

        function getUserAge(userId) {
            const user = userDatabase[userId];
            return user ? user.age : null; // Lookup + optional property access — always constant
        }
    

        function isBanned(ip) {
            return bannedIPs.has(ip); // Single hash lookup — constant time
        }
    

        function stackOperation(stack, operation, value = null) {
            if (operation === "push") {
                stack.push(value);              // O(1) amortized
                return stack;
            } else if (operation === "pop") {
                return stack.pop();             // O(1) amortized
            }
        }
    

        function calculateTax(priceObj) {
            const basePrice = priceObj.amount;
            const rate = priceObj.isLuxury ? 0.20 : 0.10;  // Conditional — constant
            const tax = basePrice * rate;                  // Arithmetic — constant
            const total = basePrice + tax + priceObj.shipping; // More constants

            return {
                tax: tax.toFixed(2),
                total: total.toFixed(2)
            };
        }
    

O(log n) — Logarithmic Time

Search space is halved each step (e.g., binary search on sorted array).

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

            while (left <= right) {
                const mid = Math.floor((left + right) / 2);
                if (arr[mid] === target) return mid;
                if (arr[mid] < target) left = mid + 1;
                else right = mid - 1;
            }
            return -1;
        }
    

        // O(log n) - Integer square root via binary search
        // Finds the largest integer whose square is <= n
        function integerSquareRoot(n) {
            if (n < 0) return -1;
            if (n === 0 || n === 1) return n;

            let left = 1;
            let right = n;
            let result = 0;

            while (left <= right) {
                const mid = Math.floor((left + right) / 2);
                // Use division to avoid overflow
                if (mid <= n / mid) {
                    result = mid;
                    left = mid + 1;     // Try larger
                } else {
                    right = mid - 1;    // Too big
                }
            }
            return result;
        }
        // Halves the range [1..n] each step → O(log n)

    

        // O(log n) - Fast exponentiation (binary exponentiation)
        // Computes base^exp efficiently
        function fastPow(base, exp) {
            if (exp === 0) return 1;
            if (exp === 1) return base;

            let result = 1;
            let currentBase = base;
            let currentExp = exp;

            while (currentExp > 0) {
                if (currentExp % 2 === 1) {
                    result *= currentBase;  // Odd exponent: multiply result
                }
                currentBase *= currentBase;  // Square the base
                currentExp = Math.floor(currentExp / 2);  // Halve the exponent
            }
            return result;
        }
        // Halves exponent each step → O(log exp)

    

        // O(log n) - Find peak element in bitonic array
        // A bitonic array increases then decreases
        function findPeak(arr) {
            let left = 0;
            let right = arr.length - 1;

            while (left < right) {
                const mid = Math.floor((left + right) / 2);
                if (arr[mid] < arr[mid + 1]) {
                    left = mid + 1;     // Peak is in right half
                } else {
                    right = mid;        // Peak is in left half (or is mid)
                }
            }
            return left; // left === right at peak
        }
        // Halves the search space each step → O(log n)

    

        // O(log n) - Search in rotated sorted array
        // Array is sorted but rotated at unknown pivot
        function searchRotated(arr, target) {
            let left = 0;
            let right = arr.length - 1;

            while (left <= right) {
                const mid = Math.floor((left + right) / 2);
                if (arr[mid] === target) return mid;

                // Check which half is sorted
                if (arr[left] <= arr[mid]) {  // Left half is sorted
                    if (target >= arr[left] && target < arr[mid]) {
                        right = mid - 1;  // Target in left sorted half
                    } else {
                        left = mid + 1;   // Target in right half
                    }
                } else {  // Right half is sorted
                    if (target > arr[mid] && target <= arr[right]) {
                        left = mid + 1;   // Target in right sorted half
                    } else {
                        right = mid - 1;  // Target in left half
                    }
                }
            }
            return -1;
        }
        // Each step eliminates half the array → O(log n)

    

O(n) — Linear Time

Time grows linearly with input size (e.g., linear search).

        // O(n) - Linear time
        // Linear search — checks each element once in the worst case
        function linearSearch(arr, target) {
            for (let i = 0; i < arr.length; i++) {
                if (arr[i] === target) return i;
            }
            return -1;
        }
    

        // O(n) - linear time 
        // find max element in an array
        function findMax(arr) {
            let max = arr[0];
            for (let i = 1; i < arr.length; i++) {
                if (arr[i] > max) {
                    max = arr[i];
                }
            }
            return max;
        }

        // Time: O(n) - one iteration through the entire array
        // Space: O(1) - only one variable to store the max value
    

        // O(n) - linear time
        // find the sum of all elements in an array
        function findSum(arr) {
            let sum = 0;
            for (let i = 0; i < arr.length; i++) {
                sum += arr[i];
            }
            return sum;
        }
        
        // Time: O(n) - one iteration through the entire array
        // Space: O(1) - only one variable to store the sum
    

        // O(n) - linear time
        // Swaps elements from both ends moving towards the center
        function reverseArray(arr) {
            let left = 0;
            let right = arr.length - 1;
            while (left < right) {
                [arr[left], arr[right]] = [arr[right], arr[left]];
                left++;
                right--;
            }
            return arr;
        }
        
        // Time: O(n) - one iteration through the entire array
        // Space: O(1) - only one variable to store the left and right pointers
    

        // O(n) - linear time
        // Scans the entire array and increments counter when match is found
        function countOccurrences(arr, target) {
            let count = 0;
            for (let i = 0; i < arr.length; i++) {
                if (arr[i] === target) {
                    count++;
                }
            }
            return count;
        }

        // Time: O(n) - one iteration through the entire array
        // Space: O(1) - only one variable to store the count
    

        // O(n) - linear time, space O(n) 
        // Create a copy of the array and reverse it
        function reverseArrayCopy(arr) {
            return arr.slice().reverse();
        }

        // Time: O(n) - one iteration through the entire array
        // Space: O(n) - creates a copy of the array
    

        // O(n) - linear time, space O(n)
        // Reverse an array by building a new array (instead of in-place swapping)
        function reverseArrayNew(arr) {
            const reversed = [];
            for (let i = arr.length - 1; i >= 0; i--) {
                reversed.push(arr[i]);
            }
            return reversed;
        }
        
        // Time: O(n) - one iteration through the entire array
        // Space: O(n) - creates a new array of the same size
    

        // O(n) - linear time, space O(n)
        // Count the frequency of each element in an array 
        function frequencyCounter(arr) {
            const frequency = {};
            for (let i = 0; i < arr.length; i++) {
                frequency[arr[i]] = (frequency[arr[i]] || 0) + 1;
            }
            return frequency;
        }
        
        // Time: O(n) - one iteration through the entire array
        // Space: O(n) - creates a new object to store the frequency
    

        // O(n) time, O(n) space
        // Convert string to uppercase by creating a new string
        // (Strings are immutable in JS, so any transformation creates new space)
        function toUpperCase(str) {
            let result = '';
            for (let i = 0; i < str.length; i++) {
                result += str[i].toUpperCase();
            }
            return result;
        }
        // Time: O(n) — processes each character once
        // Space: O(n) — builds a new string of length n
    

O(n log n) — Linearithmic Time

Typical for efficient sorting algorithms (built-in sort and merge sort).

// Built-in sort
        function sortArray(arr) {
            return arr.slice().sort((a, b) => a - b);
        }

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

        function merge(left, right) {
            let result = [];
            let i = 0, j = 0;
            while (i < left.length && j < right.length) {
                if (left[i] <= right[j]) {
                    result.push(left[i++]);
                } else {
                    result.push(right[j++]);
                }
            }
            return result.concat(left.slice(i)).concat(right.slice(j));
        }   
    

O(n²) — Quadratic Time

Nested loops over the input (e.g., bubble sort).

        function bubbleSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}

O(2ⁿ) — Exponential Time

Each step branches into two recursive calls (e.g., naive Fibonacci).

function fibonacciExponential(n) {
    if (n <= 1) return n;
    return fibonacciExponential(n - 1) + fibonacciExponential(n - 2);
}

O(n!) — Factorial Time

Generates all permutations (grows extremely fast).

function permutations(arr) {
    const result = [];

    function heapPermute(arr, n = arr.length) {
        if (n === 1) {
            result.push(arr.slice());
            return;
        }

        for (let i = 0; i < n; i++) {
            heapPermute(arr, n - 1);
            if (n % 2 === 1) {
                [arr[0], arr[n - 1]] = [arr[n - 1], arr[0]];
            } else {
                [arr[i], arr[n - 1]] = [arr[n - 1], arr[i]];
            }
        }
    }

    heapPermute(arr);
    return result;
}

Summary Table