O(2ⁿ)

O(2ⁿ): Exponential Time

Đặc điểm

• Thời gian tăng theo lũy thừa của kích thước đầu vào
• Cực kỳ chậm - chỉ phù hợp với dữ liệu nhỏ
• Thường thấy trong các bài toán đệ quy không tối ưu

Ví dụ: Fibonacci không tối ưu

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

Vấn đề với Fibonacci không tối ưu

Ví dụ tính fibonacci(5):

fib(5)
├─ fib(4)
│  ├─ fib(3)
│  │  ├─ fib(2)
│  │  │  ├─ fib(1) = 1
│  │  │  └─ fib(0) = 0
│  │  └─ fib(1) = 1
│  └─ fib(2) ← Tính lại!
│     ├─ fib(1) = 1
│     └─ fib(0) = 0
└─ fib(3) ← Tính lại toàn bộ!
   ├─ fib(2)
   │  ├─ fib(1) = 1
   │  └─ fib(0) = 0
   └─ fib(1) = 1

Vấn đề nghiêm trọng:

• Tính đi tính lại cùng một giá trị vô số lần
• Với n = 40 → cần ~2⁴⁰ phép tính (hơn 1 tỷ!)
• Giải pháp: Sử dụng Dynamic Programming hoặc Memoization
• Ví dụ trực quan: O(2ⁿ)