Common Complexities

Time Complexity Rules

• Drop constants: O(2n) → O(n)
• Drop non-dominant terms: O(n² + n) → O(n²)
• Different inputs use different variables: O(a + b)
• Amortized analysis: Average over sequence
• Best, average, worst case may differ
• Focus on worst case for upper bound

Space Complexity

Quick Examples

// O(1) - Constant
function getFirst(arr) {
    return arr[0];
}

// O(n) - Linear
function sum(arr) {
    let total = 0;
    for (let i = 0; i < arr.length; i++) {
        total += arr[i];
    }
    return total;
}

// O(n²) - Quadratic
function printPairs(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            console.log(arr[i], arr[j]);
        }
    }
}

// O(log n) - Logarithmic
function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        let 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;
}