Big O Notation & Phân Tích Độ Phức Tạp: Hướng Dẫn Toàn Diện

O(1)      → "O of 1" hoặc "constant time"
O(n)      → "O of n" hoặc "linear time"
O(log n)  → "O of log n" hoặc "logarithmic time"
O(n²)     → "O of n squared" hoặc "quadratic time"
O(2ⁿ)     → "O of 2 to the n" hoặc "exponential time"

// O(1) - Constant time
function getFirstElement<T>(arr: T[]): T | undefined {
    return arr[0];  // Luôn một operation, bất kể array size
}
 
// O(1) - Hash table lookup
function getUserAge(users: Map<string, number>, userId: string): number | undefined {
    return users.get(userId);  // Instant lookup
}

# O(1) - Constant time
def get_first_element(arr: list) -> any:
    return arr[0] if arr else None
 
# O(1) - Dictionary lookup
def get_user_age(users: dict, user_id: str) -> int:
    return users.get(user_id)

// O(log n) - Binary search
function binarySearch(arr: number[], target: number): number {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}
 
// Với 1,000,000 items, chỉ cần ~20 comparisons!

# O(log n) - Binary search
def binary_search(arr: list[int], target: int) -> int:
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

// O(n) - Linear search
function linearSearch<T>(arr: T[], target: T): number {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;
        }
    }
    return -1;
}
 
// O(n) - Sum all elements
function sum(arr: number[]): number {
    let total = 0;
    for (const num of arr) {
        total += num;
    }
    return total;
}

// O(n log n) - Merge sort
function mergeSort(arr: number[]): number[] {
    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);
}
 
// Native sort cũng là O(n log n)
console.log([...arr].sort((a, b) => a - b));

// O(n²) - Bubble sort
function bubbleSort(arr: number[]): number[] {
    const n = arr.length;
    
    for (let i = 0; i < n; i++) {           // Outer loop: n times
        for (let j = 0; j < n - i - 1; j++) {  // Inner loop: n times
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    
    return arr;
}

# O(n²) - Bubble sort
def bubble_sort(arr: list[int]) -> list[int]:
    n = len(arr)
    
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    
    return arr

// O(2ⁿ) - Naive recursive Fibonacci
function fibonacci(n: number): number {
    if (n <= 1) return n;
    
    return fibonacci(n - 1) + fibonacci(n - 2);
}
 
// Với n=30: ~2 triệu calls!

// O(2n) → đơn giản hóa thành O(n)
function printTwice(arr: number[]): void {
    arr.forEach(x => console.log(x));  // O(n)
    arr.forEach(x => console.log(x));  // O(n)
    // Total: O(2n) → O(n)
}

// O(n² + n) → đơn giản hóa thành O(n²)
function example(arr: number[]): void {
    // Loop đơn: O(n)
    for (let i = 0; i < arr.length; i++) {
        console.log(arr[i]);
    }
    
    // Nested loops: O(n²)
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            console.log(arr[i], arr[j]);
        }
    }
    
    // Total: O(n²)
}

// O(n + m) - KHÔNG PHẢI O(n)
function printBothArrays(arr1: number[], arr2: number[]): void {
    arr1.forEach(x => console.log(x));  // O(n)
    arr2.forEach(x => console.log(x));  // O(m)
    // Total: O(n + m)
}
 
// O(n × m) - KHÔNG PHẢI O(n²)
function printPairs(arr1: number[], arr2: number[]): void {
    for (const x of arr1) {       // O(n)
        for (const y of arr2) {   // O(m)
            console.log(x, y);
        }
    }
    // Total: O(n × m)
}

// O(1) space - Chỉ vài variables
function sumArray(arr: number[]): number {
    let total = 0;  // O(1) space
    for (const num of arr) {
        total += num;
    }
    return total;
}

// O(n) space - Tạo new array
function doubleArray(arr: number[]): number[] {
    const result: number[] = [];  // O(n) space
    for (const num of arr) {
        result.push(num * 2);
    }
    return result;
}

// O(n) space do call stack
function factorial(n: number): number {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // Mỗi call dùng stack space
}
 
// Maximum stack depth: n → O(n) space

// Brute force: O(n²) time, O(1) space
function twoSumBrute(arr: number[], target: number): [number, number] | null {
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[i] + arr[j] === target) {
                return [i, j];
            }
        }
    }
    return null;
}
 
// Optimized: O(n) time, O(n) space
function twoSumHash(arr: number[], target: number): [number, number] | null {
    const seen = new Map<number, number>();
    
    for (let i = 0; i < arr.length; i++) {
        const complement = target - arr[i];
        if (seen.has(complement)) {
            return [seen.get(complement)!, i];
        }
        seen.set(arr[i], i);
    }
    
    return null;
}