Độ phức tạp thuật toánAlgorithmic Complexity

Thuộc bộ kiến thức Data Structures & Algorithms Roadmap.

Tổng quan

Algorithmic complexity là môn học về việc một thuật toán tốn bao nhiêu khi input của nó lớn dần — tốn bao nhiêu thời gian và bao nhiêu memory, biểu diễn dưới dạng hàm của kích thước input n. Đây là kỹ năng mang đi được nhiều nhất trong toàn bộ roadmap này. Cấu trúc đến rồi đi, ngôn ngữ thay đổi, nhưng khả năng nhìn vào một vòng lặp và nói “cái đó là O(n²) và nó sẽ không sống nổi với dữ liệu production” thì tồn tại mãi.

Lý do ta đo tốc độ tăng trưởng thay vì đo giây là vì giây không phải là thuộc tính của thuật toán. Chạy cùng một đoạn code trên laptop và trên server, bằng Python và bằng C, với cache lạnh và cache nóng, bạn sẽ nhận được những con số chênh nhau cả trăm lần — và chẳng con số nào nói cho bạn điều gì về bản thân thuật toán. Thứ thật sự là thuộc tính của thuật toán là chi phí co giãn ra sao: nhân đôi input thì khối lượng công việc nhân đôi, nhân bốn, hay giữ nguyên? Câu hỏi đó có một câu trả lời độc lập với máy móc, và câu trả lời đó quyết định code của bạn có chạy nổi ở quy mô lớn hay không.

Mức độ nghiêm trọng rất dễ bị đánh giá thấp cho tới khi bạn đặt con số vào. Một thuật toán O(n²) với n = 1000 làm một triệu phép toán — tức thì. Cũng thuật toán đó với n = 1.000.000 làm 10¹² phép toán, với tốc độ một tỷ phép toán mỗi giây thì tương đương khoảng mười bảy phút. Trong khi đó một thuật toán O(n log n) trên cùng input một triệu phần tử chỉ làm khoảng 2 × 10⁷ phép toán: hai mươi mili giây. Không có compiler flag nào, không có CPU nhanh hơn nào, và không có bao nhiêu lần viết lại vòng lặp trong cùng nào lấp được khoảng cách năm mươi nghìn lần. Khoảng cách đó được định đoạt ngay khi bạn chọn thuật toán, và phân tích complexity là cách bạn nhìn thấy nó trước khi ship.

Ghi chú này bao gồm: đo cái gì (time vs space), suy ra complexity từ code như thế nào, những runtime bạn sẽ gặp trong thực tế, ký hiệu hình thức (O, Ω, θ) dùng để phát biểu kết quả, sự phân biệt best/average/worst case, amortized analysis, và — quan trọng không kém — chỗ mà toàn bộ khung lý thuyết này thôi không còn dự đoán tốt thời gian thực tế nữa.

Kiến thức nền tảng

Sao không cứ bấm giờ mà đo

Đo đạc thực sự hữu ích và bạn nên làm, nhưng nó không thay thế được phân tích, vì ba lý do:

1. Một phép đo là một điểm; complexity là cả đường cong. Bấm giờ function của bạn trên fixture 500 dòng chẳng nói được gì về bảng production 5.000.000 dòng. Toàn bộ kiểu thất bại của code bậc hai là ở chỗ nó trông rất ổn lúc test.
2. Phép đo bị nhiễu. Overhead của interpreter, thời gian JIT khởi động, garbage collection, trạng thái cache, việc CPU đổi tần số, và cái máy ảo hàng xóm ồn ào trên cloud — tất cả đều làm xê dịch con số. Phân tích thì không bị ảnh hưởng bởi bất cứ thứ nào trong số đó.
3. Phân tích làm được trước khi code tồn tại. Bạn có thể so sánh hai thiết kế trên bảng trắng. Bạn không thể benchmark thứ bạn chưa viết.

Quy trình đúng là làm cả hai: phân tích để chọn thuật toán, đo đạc để bắt những thứ mà phân tích đã trừu tượng hóa đi mất (hằng số, cache, hành vi của allocator). Phân tích mà không đo thì ship ra galactic algorithm; đo mà không phân tích thì ship ra code chết ở quy mô gấp 10.

Time complexity và space complexity

Time complexity đếm số phép toán sơ cấp mà thuật toán thực hiện, như một hàm của kích thước input. Space complexity đếm lượng memory nó cần, cũng như một hàm của kích thước input.

Space complexity có một điểm tinh tế đáng chốt lại. Có hai thứ bạn có thể đang muốn nói tới:

• Tổng bộ nhớ — tính cả bản thân input. Bất kỳ thuật toán nào đọc một array n phần tử đều dùng ít nhất O(n) tổng bộ nhớ.
• Bộ nhớ phụ (auxiliary space) — phần memory thuật toán cấp phát thêm ngoài input. Đây gần như luôn là con số đáng quan tâm, và khi ai đó nói “merge sort tốn O(n) bộ nhớ còn quicksort tốn O(log n)”, họ đang nói về auxiliary space.

Auxiliary space bao gồm cả những thứ bạn hay quên: recursion call stack (một frame cho mỗi lời gọi đang hoạt động, nên đệ quy sâu d tốn O(d) dù mỗi frame rất nhỏ), các array tạm, bảng memoization, và cả output nếu bạn dựng ra một cái mới thay vì sửa tại chỗ.

Thuật toán	Time	Auxiliary space	Vì sao
Tính tổng array bằng vòng lặp	O(n)	O(1)	một biến tích lũy
Binary search (lặp)	O(log n)	O(1)	hai chỉ số
Binary search (đệ quy)	O(log n)	O(log n)	một stack frame mỗi tầng
Merge sort	O(n log n)	O(n)	buffer để merge
Quicksort (in-place)	O(n log n) trung bình	O(log n) trung bình	chỉ có recursion stack
Heapsort	O(n log n)	O(1)	sắp xếp ngay trong array
Counting sort (miền giá trị k)	O(n + k)	O(k)	mảng đếm
Fibonacci đệ quy ngây thơ	O(2^n)	O(n)	độ sâu stack là n
Fibonacci có memo	O(n)	O(n)	bảng memo
Fibonacci lặp	O(n)	O(1)	hai biến

Đánh đổi space–time

Ba dòng cuối bảng trên chính là sự đánh đổi thu nhỏ. Bạn gần như luôn có thể dùng memory mua lấy thời gian, và đôi khi dùng thời gian mua lấy memory:

# O(2^n) time, O(n) space — tính đi tính lại cùng những subproblem, số lần theo hàm mũ.
def fib_naive(n):
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

# O(n) time, O(n) space — bỏ memory ra để nhớ những đáp án đã tính rồi.
def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

# O(n) time, O(1) space — để ý là bạn chỉ cần đúng hai giá trị gần nhất.
def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

fib_naive(35) mất vài giây; fib_memo(35) và fib_iter(35) là tức thì. Đây chính là toàn bộ ý tưởng đằng sau quy hoạch động. Vài trường hợp đánh đổi khác gặp hằng ngày: hash table cố tình lãng phí memory (luôn để trống một phần) để giữ lookup ở O(1); database index lưu hẳn một cấu trúc sorted riêng để việc đọc không phải quét toàn bảng; cache lưu bản sao dư thừa để một request bỏ qua được việc tính lại. Precomputation, memoization, indexing và caching đều là cùng một nước cờ.

Đánh đổi cũng đi theo chiều ngược lại. Nén dữ liệu đổi thời gian CPU lấy dung lượng nhỏ hơn. Sắp xếp in-place đổi một thuật toán phức tạp hơn chút lấy bộ nhớ phụ O(1). Bạn muốn đi chiều nào phụ thuộc vào tài nguyên nào đang khan hiếm — và trên phần cứng nhúng hay trong một ngân sách memory chật chội, space thắng.

Tính complexity từ code như thế nào

Quy trình máy móc là: đếm số phép toán như một hàm của n, rồi rút gọn bằng cách chỉ giữ lại số hạng tăng nhanh nhất và bỏ đi các hệ số hằng. Bốn quy tắc làm gần hết công việc.

Quy tắc 1 — công việc hằng số là O(1). Phép số học, so sánh, gán, truy cập array theo chỉ số, và tra hash — mỗi cái tính là một bước, bất kể giá trị lớn nhỏ ra sao.

Quy tắc 2 — các block tuần tự thì cộng. Nếu block A là O(f(n)) và block B là O(g(n)), chạy A rồi B là O(f(n) + g(n)), rút gọn thành O(max(f, g)).

Quy tắc 3 — vòng lặp lồng nhau thì nhân. Một vòng lặp chạy f(n) lần mà thân của nó tốn g(n) sẽ là O(f(n) · g(n)).

Quy tắc 4 — bỏ hằng số và các số hạng bậc thấp. 3n² + 5n + 100 là O(n²). Hằng số bị bỏ vì chúng phụ thuộc vào máy; số hạng bậc thấp bị bỏ vì với n lớn chúng vô hình bên cạnh số hạng dẫn đầu. Tại n = 10⁶, n² là 10¹² còn 5n là 5 × 10⁶ — số hạng thấp đóng góp 0,0005% tổng số.

Áp dụng vào code thật:

# --- O(1): công việc không phụ thuộc n ---
def get_middle(arr):
    return arr[len(arr) // 2]              # một phép tính chỉ số, một lần truy cập

# --- O(n): một lượt duyệt ---
def total(arr):
    s = 0                                  # 1 bước
    for x in arr:                          # n lần lặp
        s += x                             #   1 bước mỗi lần  -> n bước
    return s                               # 1 bước
                                           # 2n + 2 -> O(n)

# --- O(n): các vòng lặp tuần tự thì CỘNG, không phải nhân ---
def sum_and_max(arr):
    s = 0
    for x in arr:                          # n
        s += x
    m = arr[0]
    for x in arr:                          # + n
        m = max(m, x)
    return s, m                            # 2n -> O(n)

# --- O(n^2): vòng lặp lồng nhau thì NHÂN ---
def has_duplicate_pair(arr, target):
    for i in range(len(arr)):              # n
        for j in range(len(arr)):          #   x n
            if i != j and arr[i] + arr[j] == target:
                return True
    return False                           # n*n -> O(n^2)

# --- Vẫn là O(n^2): vòng lặp tam giác là n(n-1)/2, và hằng số thì bỏ ---
def all_pairs(arr):
    pairs = []
    for i in range(len(arr)):              # n
        for j in range(i + 1, len(arr)):   #   n-i-1, trung bình n/2
            pairs.append((arr[i], arr[j]))
    return pairs                           # n(n-1)/2 -> O(n^2)

# --- O(log n): biến lặp được NHÂN chia, không phải cộng thêm ---
def count_halvings(n):
    steps = 0
    while n > 1:                           # n -> n/2 -> n/4 -> ... -> 1
        n //= 2
        steps += 1
    return steps                           # log2(n) lần lặp -> O(log n)

# --- O(n log n): một vòng lặp tuyến tính chứa một vòng lặp logarit ---
def total_halvings(arr):
    steps = 0
    for x in arr:                          # n
        steps += count_halvings(x)         #   x O(log x)
    return steps                           # O(n log n)

# --- O(n): KHÔNG phải O(n^2). Vòng trong bị chặn tổng, không lặp lại từ đầu. ---
def longest_run(arr):
    best, i = 0, 0
    while i < len(arr):                    # trông có vẻ lồng nhau...
        j = i
        while j < len(arr) and arr[j] == arr[i]:
            j += 1                         # ...nhưng j không bao giờ lùi lại,
        best = max(best, j - i)            # nên vòng trong chỉ tiến tổng cộng
        i = j                              # n lần trên TOÀN BỘ lần chạy.
    return best                            # O(n)

Ví dụ cuối là cái người ta hay sai nhất. Lồng nhau về cú pháp không đồng nghĩa với nhân lên về chi phí. Câu hỏi đúng không bao giờ là “lồng sâu mấy tầng” mà là “dòng này thực thi tổng cộng bao nhiêu lần, trên toàn bộ lần chạy”.

Một dạng thứ hai đáng nhận diện là vòng lặp điều hòa, trông như bậc hai nhưng không phải:

# Sàng Eratosthenes: vòng lặp trong chạy n/2 + n/3 + n/5 + ... lần.
# Tổng đó là n * (tổng nghịch đảo các số nguyên tố < n) = O(n log log n).
def primes_up_to(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= n:                      # vòng ngoài: O(sqrt(n)) giá trị p
        if is_prime[p]:
            for multiple in range(p * p, n + 1, p):   # n/p bước
                is_prime[multiple] = False
        p += 1
    return [i for i, prime in enumerate(is_prime) if prime]
                                           # tổng: O(n log log n), gần như tuyến tính

Đây là bảng tóm tắt để so khớp mẫu:

Dạng code	Complexity
Số câu lệnh cố định, không vòng lặp	O(1)
Một vòng lặp qua n phần tử	O(n)
Hai vòng lặp tuần tự qua n	O(n) — chúng cộng
Vòng lặp trong vòng lặp, cả hai qua n	O(n²)
Vòng lặp lồng dạng tam giác (j bắt đầu từ i)	O(n²) — hệ số ½ bị bỏ
Ba vòng lặp lồng nhau qua n	O(n³)
while n > 1: n //= 2	O(log n)
Vòng lặp qua n có binary search hoặc thao tác heap bên trong	O(n log n)
Hai con trỏ chỉ tiến về phía trước	O(n) — tổng quãng đường bị chặn
Cửa sổ trượt qua n	O(n) — cùng lý do (./23-two-pointers-and-sliding-window.md)
Đệ quy chia đôi, gộp lại tốn O(n)	O(n log n)
Đệ quy chia đôi, công việc O(1)	O(n)
Đệ quy gọi 2 nhánh trên n-1	O(2^n)
Liệt kê mọi tập con của n phần tử	O(2^n)
Liệt kê mọi hoán vị của n phần tử	O(n!)

Complexity của code đệ quy

Vòng lặp thì bạn đếm; đệ quy thì bạn biến thành một hệ thức truy hồi — một phương trình biểu diễn chi phí cho kích thước n theo chi phí của các input nhỏ hơn — rồi giải nó.

def merge_sort(arr):
    if len(arr) <= 1:                      # base case: O(1)
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])           # T(n/2)
    right = merge_sort(arr[mid:])          # T(n/2)
    return merge(left, right)              # O(n)

def merge(a, b):
    out, i, j = [], 0, 0
    while i < len(a) and j < len(b):       # mỗi phần tử được chuyển đúng một lần
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    out.extend(a[i:]); out.extend(b[j:])
    return out                             # O(len(a) + len(b))

Hệ thức truy hồi là T(n) = 2T(n/2) + O(n), với T(1) = O(1). Vẽ recursion tree ra: mỗi tầng làm tổng cộng O(n) công việc (các lần merge ở tầng đó phủ mỗi phần tử đúng một lần), và có log₂ n tầng vì kích thước giảm một nửa mỗi lần. Vậy T(n) = O(n log n).

Master Theorem biến việc này thành tra bảng cho các hệ thức dạng T(n) = a·T(n/b) + f(n):

Hệ thức truy hồi	Nghiệm	Ví dụ
T(n) = T(n/2) + O(1)	O(log n)	binary search
T(n) = T(n/2) + O(n)	O(n)	quickselect (trung bình)
T(n) = 2T(n/2) + O(1)	O(n)	duyệt cây, heapify
T(n) = 2T(n/2) + O(n)	O(n log n)	merge sort, quicksort (trung bình)
T(n) = 2T(n/2) + O(n²)	O(n²)	công việc ở tầng trên cùng áp đảo
T(n) = T(n-1) + O(1)	O(n)	đệ quy tuyến tính, tính tổng list
T(n) = T(n-1) + O(n)	O(n²)	quicksort worst case, selection sort
T(n) = 2T(n-1) + O(1)	O(2^n)	Fibonacci ngây thơ, Tháp Hà Nội
T(n) = n·T(n-1) + O(1)	O(n!)	sinh mọi hoán vị

Phần suy diễn được triển khai đầy đủ trong ./19-recursion-and-divide-and-conquer.md.

Khái niệm chính

Asymptotic notation

Asymptotic notation mô tả hành vi tiệm cận của một hàm khi đối số của nó lớn dần, bỏ đi các hệ số hằng và các số hạng bậc thấp. Ba ký hiệu gánh gần như toàn bộ trọng lượng, và chúng nói những điều khác nhau — một sự phân biệt mà người ta thường xuyên làm mờ đi.

Big-O — cận trên. f(n) = O(g(n)) nếu tồn tại các hằng số dương c và n₀ sao cho

0 ≤ f(n) ≤ c · g(n)    với mọi n ≥ n₀

Nói bằng lời: vượt qua một kích thước input nào đó, f tăng không nhanh hơn g, sai khác một hệ số hằng. Big-O là cái trần. Đây là ký hiệu bạn gặp nhiều nhất vì trong thực tế bạn quan tâm nhất tới “tệ nhất thì có thể tệ tới đâu”.

Big-Ω — cận dưới. f(n) = Ω(g(n)) nếu tồn tại các hằng số dương c và n₀ sao cho

0 ≤ c · g(n) ≤ f(n)    với mọi n ≥ n₀

Vượt qua một kích thước input nào đó, f tăng ít nhất là nhanh bằng g. Big-Ω là cái sàn. Công dụng quan trọng nhất của nó là phát biểu giới hạn cho bài toán chứ không phải cho thuật toán: “mọi thuật toán sắp xếp dựa trên so sánh đều cần Ω(n log n) phép so sánh” là một khẳng định rằng không thuật toán nào, hiện tại hay tương lai, phá được cận đó — và đó là điều khiến merge sort và heapsort tối ưu một cách có chứng minh trong mô hình đó (./08-sorting-algorithms.md).

Big-θ — cận chặt. f(n) = θ(g(n)) nếu tồn tại các hằng số dương c₁, c₂ và n₀ sao cho

0 ≤ c₁ · g(n) ≤ f(n) ≤ c₂ · g(n)    với mọi n ≥ n₀

Tương đương, θ(g) = O(g) ∩ Ω(g): f bị kẹp giữa g từ cả hai phía, nên g chính xác là tốc độ tăng trưởng. Đây thường là mô tả trung thực về chi phí của một thuật toán, và cũng là điều mà phần lớn mọi người muốn nói khi họ nói Big-O.

Hai ký hiệu nữa, ít dùng hơn nhưng đáng nhận biết:

• little-o — f(n) = o(g(n)) nghĩa là f tăng nghiêm ngặt chậm hơn: bất đẳng thức đúng với mọi c dương, không chỉ với một c nào đó. n = o(n²) là đúng; n² = o(n²) là sai.
• little-ω — phiên bản nghiêm ngặt của Ω. n² = ω(n).

Ký hiệu	Ý nghĩa	Tương tự như	Dùng điển hình
O(g)	tăng không nhanh hơn g	≤	”thuật toán này tốn nhiều nhất là…”
Ω(g)	tăng ít nhất nhanh bằng g	≥	”bài toán này đòi hỏi ít nhất là…”
θ(g)	tăng đúng bằng g	=	”đây là tốc độ tăng trưởng thật”
o(g)	tăng nghiêm ngặt chậm hơn g	<	tách các lớp complexity
ω(g)	tăng nghiêm ngặt nhanh hơn g	>	tách các lớp complexity

Một chứng minh mẫu, vì các định nghĩa dễ tin hơn sau khi bạn đã dùng chúng một lần. Khẳng định: 3n² + 5n + 2 = θ(n²).

• Cận trên. Với n ≥ 1 ta có n ≤ n² và 1 ≤ n², nên 3n² + 5n + 2 ≤ 3n² + 5n² + 2n² = 10n². Lấy c₂ = 10, n₀ = 1. Vậy là O(n²).
• Cận dưới. Với n ≥ 1, 3n² + 5n + 2 ≥ 3n². Lấy c₁ = 3, n₀ = 1. Vậy là Ω(n²).
• Cả hai đều đúng, nên θ(n²). ∎

Hai cái bẫy về ký hiệu. Thứ nhất, dấu = trong f(n) = O(g(n)) là một sự lạm dụng ký hiệu — O(g(n)) là một tập hợp các hàm, và phát biểu trung thực phải là f(n) ∈ O(g(n)). Hệ quả là quan hệ này không đối xứng: bạn có thể viết f(n) = O(n²) nhưng không bao giờ được viết O(n²) = f(n).

Thứ hai, Big-O là cận trên, không phải lời hứa về sự chặt chẽ. Binary search là O(log n), và nó cũng — hoàn toàn đúng — là O(n), O(n²) và O(2^n), vì tất cả đều là những cái trần hợp lệ. Nói “binary search là O(n²)” vừa đúng vừa vô dụng. Khi ai đó phát biểu một complexity, họ gần như luôn có ý nói tới cận chặt nhất mà họ biết, tức là θ; quy ước này vô hại miễn là bạn nhớ rằng riêng O không cấm thuật toán chạy nhanh hơn.

Các runtime thường gặp

Lớp	Tên	Nhân đôi n thì công việc thế nào?	Ví dụ kinh điển
O(1)	Hằng số	không đổi	truy cập array theo chỉ số, tra hash
O(log n)	Logarit	thêm một bước	binary search
O(n)	Tuyến tính	nhân đôi	quét tuyến tính
O(n log n)	Tuyến tính-logarit	nhiều hơn gấp đôi một chút	merge sort
O(n²), O(n³), O(n^k)	Đa thức	×4, ×8, ×2^k	bubble sort, nhân ma trận
O(2^n)	Hàm mũ	bình phương lên	liệt kê tập con
O(n!)	Giai thừa	không tả nổi	TSP vét cạn

O(1) — hằng số. Thời gian chạy độc lập với kích thước input. Truy cập arr[i] tốn như nhau dù array chứa mười phần tử hay mười triệu, vì địa chỉ được tính bằng số học chứ không phải đi tìm. Lưu ý “hằng số” không có nghĩa là “nhanh” — một thao tác hằng số có thể gồm cả nghìn lệnh; nó chỉ có nghĩa là số lượng đó không tăng theo n.

def get(arr, i):
    return arr[i]                          # address = base + i*size: O(1)

def is_even(n):
    return n % 2 == 0                      # O(1)

O(log n) — logarit. Thuật toán loại bỏ một tỉ lệ hằng số của phần input còn lại ở mỗi bước, nên số bước bằng số lần bạn chia đôi được n trước khi chạm 1. Đây là tốc độ tăng trưởng cực kỳ tốt: log₂ của một triệu là 20, của một tỷ là 30. Thêm dữ liệu gấp một nghìn lần chỉ thêm mười bước.

def binary_search(arr, target):
    """arr phải đã sorted. Chia đôi khoảng tìm kiếm ở mọi vòng lặp."""
    lo, hi = 0, len(arr) - 1
    while lo <= hi:                        # khoảng: n, n/2, n/4, ... 1
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1                   # bỏ nguyên nửa dưới
        else:
            hi = mid - 1                   # bỏ nguyên nửa trên
    return -1                              # O(log n) lần lặp

Các thành viên khác: insert/search trong balanced BST, push/pop trên binary heap, lũy thừa bằng bình phương liên tiếp, đếm số chữ số của một số.

O(n) — tuyến tính. Công việc tăng tỉ lệ thuận với input, đó là thứ bạn nhận được khi phải nhìn mọi phần tử đúng một lần. Với nhiều bài toán, đây là tối ưu, bởi bạn không thể quyết định được đáp án mà không đọc input: tìm phần tử lớn nhất của một array chưa sorted bắt buộc phải Ω(n), vì bất kỳ phần tử nào bạn bỏ qua đều có thể là phần tử lớn nhất.

def maximum(arr):
    best = arr[0]
    for x in arr:                          # chạm mọi phần tử đúng một lần
        if x > best:
            best = x
    return best                            # O(n)

O(n log n) — tuyến tính-logarit. Thường phát sinh từ việc làm O(log n) công việc cho mỗi phần tử trong n phần tử, hoặc từ chia để trị chia đôi và làm công việc tuyến tính ở mỗi tầng. Đây là complexity của các thuật toán sắp xếp tổng quát tốt, và nó đủ gần tuyến tính để trong thực tế được coi là rẻ: với n = 10⁶, log₂ n chỉ là 20.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))
    # log n tầng đệ quy x O(n) công merge mỗi tầng = O(n log n)

O(n^k) — đa thức. k vòng lặp lồng nhau, mỗi vòng chạy n lần. Bậc hai (k = 2) là ngựa thồ của các thuật toán ngây thơ — so sánh mọi cặp — và là lớp complexity đầu tiên thật sự gây đau ở quy mô lớn. Bậc ba (k = 3) là phép nhân ma trận tiêu chuẩn và Floyd–Warshall tìm đường đi ngắn nhất mọi cặp. Thời gian đa thức là ranh giới hình thức của “khả thi” trong lý thuyết complexity, nhưng về mặt kỹ thuật thì bất cứ thứ gì vượt n³ thường đã bất khả thi rồi.

def bubble_sort(arr):
    """So sánh mọi cặp kề nhau, lặp đi lặp lại: O(n^2)."""
    a = list(arr)
    n = len(a)
    for i in range(n):                     # n lượt
        swapped = False
        for j in range(n - i - 1):         #   tối đa n phép so sánh mỗi lượt
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:                    # thoát sớm làm BEST case thành O(n)
            break
    return a                               # worst và average: O(n^2)

def matrix_multiply(A, B):
    """Ba vòng lặp lồng nhau tiêu chuẩn: O(n^3)."""
    n = len(A)
    C = [[0] * n for _ in range(n)]
    for i in range(n):                     # n
        for j in range(n):                 #   x n
            for k in range(n):             #     x n
                C[i][j] += A[i][k] * B[k][j]
    return C                               # O(n^3)

O(2^n) — hàm mũ. Mỗi phần tử input thêm vào sẽ nhân đôi khối lượng công việc. Đây là dấu hiệu của những thuật toán phải xét mọi tập con, hoặc của đệ quy phân nhánh hai lần mà không memo. Nó chỉ dùng được với n rất nhỏ: khoảng 25 đến 30 phần tử là trần thực tế, và tại n = 60 thì bạn đã vượt quá số nano giây trôi qua kể từ thời khủng long.

def all_subsets(items):
    """Có 2^n tập con, nên chỉ riêng việc liệt kê chúng đã là O(2^n)."""
    result = [[]]
    for x in items:                        # mỗi phần tử nhân đôi kích thước kết quả
        result += [subset + [x] for subset in result]
    return result                          # O(2^n) time và O(2^n) space

def fib_naive(n):
    """Hai lời gọi đệ quy mỗi tầng, độ sâu n: khoảng 2^n lời gọi."""
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)   # O(2^n) — thật ra là O(phi^n)

Hàm mũ thường là triệu chứng chứ không phải điều bắt buộc. fib_naive là hàm mũ thuần túy vì nó tính lại cùng những subproblem; memo nó lại là thành tuyến tính. Nhận ra các subproblem lặp lại và loại bỏ chúng là kỹ năng cốt lõi của quy hoạch động.

O(n!) — giai thừa. Số cách sắp xếp thứ tự n phần tử. Nó xuất hiện mỗi khi một thuật toán thử mọi hoán vị: TSP vét cạn, xếp lịch vét cạn, giải đố ngây thơ. Nó tăng nhanh hơn cả hàm mũ và không dùng được quá khoảng n = 11. 13! đã vượt sáu tỷ.

def permutations(items):
    """n! cách sắp xếp; sinh hết chúng là O(n * n!)."""
    if len(items) <= 1:
        return [list(items)]
    out = []
    for i in range(len(items)):            # n lựa chọn cho phần tử đầu tiên
        rest = items[:i] + items[i + 1:]
        for p in permutations(rest):       #   x (n-1)! cách sắp xếp phần còn lại
            out.append([items[i]] + p)
    return out                             # O(n!)

def tsp_bruteforce(dist):
    """Thử mọi hành trình. n! ứng viên — đúng, và vô vọng quá n ~ 11."""
    n = len(dist)
    best = float("inf")
    for order in permutations(list(range(1, n))):
        tour = [0] + order + [0]
        cost = sum(dist[tour[i]][tour[i + 1]] for i in range(len(tour) - 1))
        best = min(best, cost)
    return best

Tốc độ tăng trưởng thật sự quan trọng đến mức nào

Các lớp trừu tượng trở nên thuyết phục khi bạn đặt con số vào. Bảng này cho số bước xấp xỉ của từng lớp ở ba kích thước input.

Complexity	n = 10	n = 1000	n = 1.000.000
O(1)	1	1	1
O(log n)	3	10	20
O(√n)	3	32	1.000
O(n)	10	1.000	1.000.000
O(n log n)	33	9.966	19.931.569
O(n²)	100	1.000.000	1012
O(n³)	1.000	109	1018
O(2^n)	1.024	~10301	không mô tả nổi
O(n!)	3.628.800	~102568	không mô tả nổi

Cùng bảng đó quy đổi ra thời gian thực, giả định lạc quan 10⁹ phép toán sơ cấp mỗi giây:

Complexity	n = 10	n = 1000	n = 1.000.000
O(log n)	< 1 ns	< 1 ns	20 ns
O(n)	10 ns	1 µs	1 ms
O(n log n)	33 ns	10 µs	20 ms
O(n²)	100 ns	1 ms	17 phút
O(n³)	1 µs	1 giây	31 năm
O(2^n)	1 µs	lâu hơn tuổi vũ trụ	—
O(n!)	3,6 ms	lâu hơn tuổi vũ trụ	—

Câu hỏi ngược lại mới là câu bạn thật sự đặt ra trong competitive programming và trong hoạch định năng lực: cho khoảng một giây tính toán, complexity này xử lý được n lớn tới đâu?

Complexity	n khả thi trong ~1 giây
O(log n)	gần như không giới hạn
O(n)	~108
O(n log n)	~106 – 107
O(n²)	~104
O(n³)	~500
O(2^n)	~25
O(n!)	~11

Đọc ngược bảng này thì nó thành một công cụ thiết kế. Nếu đề bài nói n ≤ 10⁵ thì lời giải O(n²) là 10¹⁰ phép toán và sẽ không qua được — bạn cần O(n log n) hoặc tốt hơn, điều này lập tức gợi ý tới sorting, heap, hash map hoặc binary search. Nếu n ≤ 20 thì liệt kê tập con theo hàm mũ là ổn và bạn nên dừng việc tìm cách gì thông minh hơn.

Best case, average case, worst case

Complexity không chỉ phụ thuộc vào kích thước input mà còn vào nội dung của nó. Với một n cho trước, có input dễ và có input khó, nên ta mô tả ba trường hợp:

• Best case — input rẻ nhất trong các input kích thước n. Thường là con số ít hữu ích nhất: nó hay là một trường hợp giả tạo (array vốn đã sorted, target tìm thấy ngay lần dò đầu tiên) và nó không bao giờ cho bạn biết hệ thống có trụ nổi hay không.
• Worst case — input đắt nhất trong các input kích thước n. Đây là mặc định, và đúng là nên vậy: nó là một bảo đảm, nó là thứ mà SLO về latency và các hệ thống real-time cần, và input đối nghịch — một user có quyền chọn dữ liệu — biến “khó xảy ra” thành “mọi request”.
• Average case — chi phí kỳ vọng trên một phân phối input nào đó. Phản ánh hành vi thông thường tốt hơn, nhưng nó buộc bạn phải nêu rõ phân phối, và phân phối trung thực thì thường không biết được.

Thuật toán	Best	Average	Worst	Vì sao worst khác
Linear search	O(1)	O(n)	O(n)	target ở cuối hoặc không có
Binary search	O(1)	O(log n)	O(log n)	target trúng ngay điểm giữa đầu tiên
Insertion sort	O(n)	O(n²)	O(n²)	đã sorted vs sorted ngược
Bubble sort (có thoát sớm)	O(n)	O(n²)	O(n²)	một lượt sạch vs sorted ngược
Selection sort	O(n²)	O(n²)	O(n²)	luôn quét hết phần còn lại — không có best case
Merge sort	O(n log n)	O(n log n)	O(n log n)	luôn chia đôi bất kể nội dung
Quicksort	O(n log n)	O(n log n)	O(n²)	pivot luôn là min/max → phân hoạch cỡ 1 và n−1
Heapsort	O(n log n)	O(n log n)	O(n log n)	hình dạng heap không phụ thuộc nội dung
Tra cứu hash table	O(1)	O(1)	O(n)	mọi key va chạm vào cùng một bucket
Tìm trong BST (mất cân bằng)	O(log n)	O(log n)	O(n)	chèn dữ liệu sorted → suy biến thành list
Tìm trong AVL / red-black	O(log n)	O(log n)	O(log n)	cân bằng lại giúp chặn chiều cao

Hai dòng trong bảng đáng dừng lại, vì khoảng cách giữa average và worst không chỉ là lý thuyết — nó là một bề mặt tấn công.

Quicksort chọn một pivot và phân hoạch quanh nó. Với pivot tốt thì các phân hoạch cân bằng và hệ thức truy hồi là T(n) = 2T(n/2) + O(n) = O(n log n). Với pivot tệ nhất (luôn là phần tử nhỏ nhất hoặc lớn nhất) thì các phân hoạch có cỡ 0 và n−1, cho ra T(n) = T(n−1) + O(n) = O(n²). Một implementation ngây thơ luôn chọn arr[0] sẽ rơi vào worst case với input vốn đã sorted, một tình huống phổ biến đến mức đáng buồn trong thực tế. Chọn pivot ngẫu nhiên hoặc dùng median-of-three biến worst case từ chuyện thường ngày thành chuyện hầu như không thể xảy ra.

Hash table tụt xuống O(n) khi mọi key rơi vào cùng một bucket. Điều này không phải giả thuyết: hash flooding là một kỹ thuật từ chối dịch vụ có thật, trong đó kẻ tấn công gửi lên những key được chọn sao cho va chạm nhau, biến mọi lần chèn O(1) thành một lần quét O(n) và hạ gục server chỉ với lưu lượng khiêm tốn. Cách khắc phục — hash seed ngẫu nhiên theo từng process — nay đã là tiêu chuẩn trong Python, Ruby và JVM (./07-hash-tables.md).

Một làm rõ then chốt: best/average/worst là một trục hoàn toàn tách biệt với O/Ω/θ. Cái thứ nhất nói bạn đang phân tích input nào; cái thứ hai nói bạn đang phát biểu loại cận nào. Bạn có thể kết hợp chúng thoải mái và việc đó có ý nghĩa thật sự:

• “Worst case của quicksort là θ(n²)” — một cận chặt trên input tệ nhất.
• “Best case của quicksort là Ω(n log n)” — ngay cả input may mắn nhất cũng cần ít nhất chừng đó.
• “Insertion sort là O(n²)” — một cận trên bao phủ mọi input.

Nói “average case của Big-O” là một lỗi phạm trù; hai ý tưởng này không ghép với nhau theo kiểu đó.

Amortized analysis

Có những thao tác thường rẻ nhưng thỉnh thoảng cực đắt. Chỉ báo cáo worst case cho một thao tác đơn lẻ sẽ gây hiểu lầm nếu trường hợp đắt đỏ đó không thể xảy ra thường xuyên. Amortized analysis đo chi phí trung bình cho mỗi thao tác trên một chuỗi thao tác tệ nhất.

Ví dụ kinh điển là dynamic array đang lớn dần. Append bình thường là O(1) — ghi vào ô trống kế tiếp. Nhưng khi array đầy, nó phải cấp phát một khối lớn hơn và copy toàn bộ sang: O(n). Vậy một lần append là O(n) ở worst case. Thế thì append có phải là thao tác đắt không?

Không — vì bước đắt đỏ đó trả tiền cho những bước rẻ theo sau. Nếu dung lượng nhân đôi ở mỗi lần resize thì bắt đầu từ dung lượng 1 và append n phần tử, các lần resize sẽ copy tổng cộng

1 + 2 + 4 + 8 + ... + n/2 + n  <  2n   phần tử

Cấp số nhân đó có tổng nhỏ hơn 2n, nên n lần append tốn tổng cộng O(n), tức là O(1) amortized cho mỗi lần append. Việc nhân đôi là thiết yếu: nếu thay bằng tăng thêm một lượng cố định k thì sẽ cần n/k lần resize copy k, 2k, 3k, …, n phần tử — một tổng O(n²/k), khiến mỗi lần append thành O(n) amortized. Đây chính xác là lý do list trong Python, vector trong C++, và slice trong Go đều lớn lên theo cấp số nhân.

class DynamicArray:
    """Một dynamic array xây trên vùng lưu trữ kích thước cố định, để lộ ra bước
    resize mà list của Python giấu đi. Append là O(1) amortized."""

    def __init__(self):
        self._capacity = 1
        self._size = 0
        self._data = [None] * self._capacity

    def append(self, x):
        if self._size == self._capacity:   # hiếm: chỉ xảy ra log2(n) lần tổng cộng
            self._resize(self._capacity * 2)
        self._data[self._size] = x         # thường gặp: O(1)
        self._size += 1

    def _resize(self, new_capacity):
        bigger = [None] * new_capacity     # cấp phát O(n)
        for i in range(self._size):        # copy O(n)
            bigger[i] = self._data[i]
        self._data = bigger
        self._capacity = new_capacity

    def __getitem__(self, i):
        if not 0 <= i < self._size:
            raise IndexError(i)
        return self._data[i]               # luôn là O(1)

    def __len__(self):
        return self._size


a = DynamicArray()
for i in range(1000):                      # 1000 lần append, ~10 lần resize,
    a.append(i)                            # tổng cộng < 2000 lần copy phần tử
assert len(a) == 1000 and a[999] == 999

Ba kỹ thuật tiêu chuẩn để chứng minh cận amortized:

• Phương pháp tổng hợp (aggregate) — chặn tổng chi phí của n thao tác, rồi chia cho n. Lập luận cấp số nhân ở trên chính là phương pháp này.
• Phương pháp kế toán (banker’s) — tính cho mỗi thao tác một mức giá amortized do ta đặt ra, để dành phần dư làm tín dụng, rồi tiêu tín dụng đó vào các thao tác đắt. Tính 3 đơn vị cho mỗi lần append: 1 để ghi phần tử, 1 để dành cho việc copy nó ở lần resize tới, 1 để dành cho việc copy một phần tử cũ đã hết tín dụng. Số dư ngân hàng không bao giờ âm, nên tổng chi phí thật nhiều nhất là 3n.
• Phương pháp thế năng (potential) — định nghĩa một hàm thế năng Φ trên trạng thái của cấu trúc và định nghĩa chi phí amortized bằng chi phí thật cộng ΔΦ. Với dynamic array, Φ = 2·size − capacity là đủ dùng: nó tăng lên trong các lần append rẻ, và nó vừa đủ lớn để trả cho lần copy khi resize xảy ra.

Amortized không giống average case. Average case mang tính xác suất — nó phụ thuộc vào giả định về phân phối input, và một user xui xẻo có thể phá vỡ nó. Amortized là một bảo đảm worst-case tất định trên cả chuỗi: không kẻ nào dựng được n lần append tốn hơn O(n) tổng cộng. Đó là một khẳng định mạnh hơn nhiều, và đó là lý do “amortized O(1)” an toàn để dựa vào trong một ngân sách latency, còn “average O(1)” thì cần có kế hoạch cho phần đuôi phân phối.

Chỗ bạn gặp cận amortized trong thực tế:

Thao tác	Amortized	Worst case cho một lần	Cơ chế
Append dynamic array	O(1)	O(n)	nhân đôi dung lượng
Insert vào hash table	O(1)	O(n)	rehash khi vượt load factor
find của Union-Find	O(α(n))	O(log n)	path compression + union by rank
Truy cập splay tree	O(log n)	O(n)	các phép xoay tái cấu trúc cây
Tăng một bộ đếm nhị phân	O(1) mỗi lần tăng	O(log n)	hầu hết lần tăng chỉ lật một bit

α(n) là hàm Ackermann ngược, có giá trị nhiều nhất là 4 với mọi n vừa trong vũ trụ quan sát được — coi như hằng số (./16-disjoint-set-union-find.md).

Chỗ mô hình thôi không còn dự đoán được thực tế

Phân tích complexity là một mô hình, và mọi mô hình đều có miền hiệu lực. Bốn thứ nó cố tình bỏ qua, và mỗi thứ đều có thể áp đảo các phép đo thực tế.

1. Hằng số quan trọng khi n nhỏ. Ký hiệu O bỏ đi các hệ số hằng, nhưng cái máy thì không. Insertion sort là θ(n²) còn merge sort là θ(n log n), vậy mà insertion sort lại nhanh hơn với array khoảng 10 đến 50 phần tử, vì hệ số hằng của nó rất nhỏ: không cấp phát, không đệ quy, không copy, và một vòng lặp trong gọn gàng với locality hoàn hảo. Đây không phải chuyện lạ đời — các thuật toán sắp xếp production khai thác đúng điều này. Timsort (sorted của Python, Arrays.sort cho object của Java) chạy insertion sort trên các đoạn nhỏ hơn một ngưỡng rồi merge kết quả. Introsort (std::sort của C++) chạy quicksort, chuyển sang heapsort khi đệ quy đi quá sâu để tránh trường hợp O(n²), và kết thúc bằng insertion sort trên phần dư nhỏ. Lý thuyết chọn thuật toán tiệm cận; hằng số chọn ngưỡng cắt.

2. Phân cấp memory không phẳng. Mô hình RAM từ ./01-programming-fundamentals-and-pseudocode.md tính O(1) cho mọi lần truy cập memory. Phần cứng thật tính giá khác nhau một trời một vực:

Truy cập	Độ trễ xấp xỉ	Tương đối
L1 cache	~1 ns	1×
L2 cache	~4 ns	4×
L3 cache	~15 ns	15×
Main memory (RAM)	~100 ns	100×
NVMe SSD	~100 µs	100.000×
Đĩa từ (seek)	~10 ms	10.000.000×

Duyệt một array và duyệt một linked list đều là θ(n), nhưng array chảy tuần tự qua các cache line còn linked list phải đuổi theo pointer tới những địa chỉ ngẫu nhiên, gần như trượt cache mọi lần. Khoảng cách đo được thường xuyên là 5–10×. Đây cũng là toàn bộ lý do B-tree tồn tại: khi đơn vị chi phí là một page trên đĩa thay vì một phép so sánh, bạn muốn cây thấp và rộng, và log₂ n so với log₂₅₆ n là khác biệt giữa 30 lần đọc và 4 lần (../../postgresql-dba/vi/08-indexing-strategies.md).

3. Những điều hư cấu khác của mô hình RAM. Nó giả định mọi phép số học tốn một đơn vị bất kể độ lớn toán hạng — sai với số nguyên độ chính xác tùy ý, nơi nhân hai số d chữ số không phải O(1). Nó giả định một bộ xử lý duy nhất, nên chẳng nói gì về tăng tốc song song. Nó bỏ qua branch prediction, SIMD, chi phí cấp phát, và các lần dừng của garbage collector. Không điều nào trong số đó làm mô hình sai; chúng chỉ làm nó thành một mô hình bậc nhất mà phần sai số còn lại bạn xử lý bằng cách đo đạc.

4. Tốt hơn về mặt tiệm cận có thể vô dụng về mặt thực tế. Những thuật toán mà lợi thế chỉ hiện ra ở kích thước input lớn hơn bất cứ thứ gì từng tồn tại được gọi là galactic algorithm. Phép nhân ma trận có các cận đã biết quanh O(n^2.37), nhưng hệ số hằng lớn khủng khiếp đến mức phương pháp O(n³) trong sách giáo khoa — hoặc phương pháp Strassen O(n^2.807) — thắng với mọi ma trận mà con người thực sự nhân. Câu hỏi đúng không bao giờ là “cái nào có số mũ nhỏ hơn” mà là “cái nào nhanh hơn ở n của tôi”.

Một điểm thực tế liên quan: trong thực tế n thường bị chặn. Nếu function của bạn sắp xếp các món trong giỏ hàng thì n < 100 mãi mãi, và khác biệt giữa O(n²) và O(n log n) là con số không. Bỏ cả buổi chiều ra thay thuật toán sắp xếp còn tệ hơn cả lãng phí — nó thêm rủi ro mà chẳng được lợi gì. Phân tích complexity cho bạn biết vách đá ở đâu; việc của bạn là biết input của mình có thể bước hụt xuống đó hay không.

Best Practices

• Ghi complexity của mọi function không tầm thường bạn viết, trong comment hoặc docstring. Việc đó tốn vài giây, nó buộc bạn thật sự kiểm tra lại, và nó là mẩu tài liệu hữu ích nhất cho người sau này gọi function đó trong một vòng lặp.
• Mặc định phân tích worst case. Đó là một bảo đảm chứ không phải một hy vọng, và đó là thứ mà kẻ tấn công hoặc một phân phối dữ liệu production xui xẻo sẽ tìm ra. Hãy nêu average như thông tin bổ sung, đừng bao giờ đặt nó làm tiêu đề.
• Nói θ khi bạn có ý là θ. “Bubble sort là O(n²)” thì đúng nhưng yếu; “bubble sort là θ(n²) ở worst và average case, θ(n) với input đã sorted” là toàn cảnh trong một dòng.
• Tính ra con số thật trước khi tối ưu. Cắm n thật của bạn vào bảng tăng trưởng. O(n²) tại n = 200 là 40.000 phép toán — 40 micro giây, chẳng phải vấn đề. Lớp complexity mô tả sự co giãn; chỉ có phép tính số học mới nói cho bạn biết đoạn code này có chậm hay không.
• Săn tìm những chỗ vô tình bậc hai. Chúng là bug hiệu năng thực tế phổ biến nhất và vô hình trong các test nhỏ. Những nghi phạm quen thuộc: một phép kiểm tra in tuyến tính đặt trong vòng lặp, list.pop(0) hoặc insert(0, …) trong vòng lặp, nối chuỗi bằng += trong vòng lặp, một truy vấn ORM đặt trong vòng lặp (bài toán N+1), hoặc list.remove() trong vòng lặp.
• Đừng quên space, kể cả call stack. Một lời giải đệ quy sâu n tầng dùng O(n) stack — và giới hạn đệ quy mặc định 1000 của Python sẽ chặn bạn từ rất lâu trước khi memory kịp cạn. Hãy chuyển đệ quy sâu thành vòng lặp với một stack tường minh.
• Ưu tiên thuật toán mà bạn sống chung được với worst case của nó. Giữa quicksort (O(n log n) trung bình, O(n²) worst) và heapsort (O(n log n) luôn luôn), hãy chọn dựa trên việc một cú vọt latency ở phần đuôi có chấp nhận được không. Nếu đó là request hướng người dùng với SLO cứng thì cận được bảo đảm đáng giá hơn cái hằng số chậm hơn.
• Ngẫu nhiên hóa hoặc cân bằng lại khi worst case có thể chạm tới. Pivot ngẫu nhiên cho quicksort, hash có seed cho hash table, cây tự cân bằng thay vì BST thường. Những thứ này biến “tệ với input đối nghịch hoặc đã sorted” thành “tệ với xác suất không đáng kể”.
• Đo đạc sau khi phân tích. Phân tích chọn thuật toán; profiling tìm ra các hệ số hằng, cache miss, và lượng cấp phát rác mà phân tích đã trừu tượng hóa đi. Đừng bao giờ tối ưu theo linh cảm — hãy profile trước, và xác nhận cải thiện bằng benchmark trên kích thước input thực tế.
• Thuộc lòng complexity của standard library. Phần lớn các chỗ vô tình bậc hai đến từ việc tưởng một built-in là O(1) trong khi nó là O(n). Bảng TimeComplexity của Python đáng đọc kỹ một lần cho tử tế.

Tài liệu tham khảo

• roadmap.sh — Data Structures & Algorithms
• Big-O Cheat Sheet
• Big O notation — Wikipedia
• Time complexity — Wikipedia
• Space complexity — Wikipedia
• Amortized analysis — Wikipedia
• Master theorem (analysis of algorithms) — Wikipedia
• Galactic algorithm — Wikipedia
• CLRS — Introduction to Algorithms, Chapters 3 (Growth of Functions), 4 (Divide-and-Conquer), 17 (Amortized Analysis)
• MIT 6.006 — Introduction to Algorithms (OpenCourseWare)
• cp-algorithms — Sieve of Eratosthenes
• Python Wiki — TimeComplexity of built-in types
• Python Documentation — timeit for measuring small code snippets

# O(2^n) time, O(n) space — recomputes the same subproblems exponentially often.
def fib_naive(n):
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

# O(n) time, O(n) space — spend memory to remember answers you already computed.
def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

# O(n) time, O(1) space — notice you only ever need the last two values.
def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

# --- O(1): work independent of n ---
def get_middle(arr):
    return arr[len(arr) // 2]              # one index computation, one access

# --- O(n): one pass ---
def total(arr):
    s = 0                                  # 1 step
    for x in arr:                          # n iterations
        s += x                             #   1 step each  -> n steps
    return s                               # 1 step
                                           # 2n + 2 -> O(n)

# --- O(n): sequential loops ADD, they do not multiply ---
def sum_and_max(arr):
    s = 0
    for x in arr:                          # n
        s += x
    m = arr[0]
    for x in arr:                          # + n
        m = max(m, x)
    return s, m                            # 2n -> O(n)

# --- O(n^2): nested loops MULTIPLY ---
def has_duplicate_pair(arr, target):
    for i in range(len(arr)):              # n
        for j in range(len(arr)):          #   x n
            if i != j and arr[i] + arr[j] == target:
                return True
    return False                           # n*n -> O(n^2)

# --- Still O(n^2): a triangular loop is n(n-1)/2, and constants drop ---
def all_pairs(arr):
    pairs = []
    for i in range(len(arr)):              # n
        for j in range(i + 1, len(arr)):   #   n-i-1 on average n/2
            pairs.append((arr[i], arr[j]))
    return pairs                           # n(n-1)/2 -> O(n^2)

# --- O(log n): the loop variable is MULTIPLIED, not incremented ---
def count_halvings(n):
    steps = 0
    while n > 1:                           # n -> n/2 -> n/4 -> ... -> 1
        n //= 2
        steps += 1
    return steps                           # log2(n) iterations -> O(log n)

# --- O(n log n): a linear loop containing a logarithmic one ---
def total_halvings(arr):
    steps = 0
    for x in arr:                          # n
        steps += count_halvings(x)         #   x O(log x)
    return steps                           # O(n log n)

# --- O(n): NOT O(n^2). The inner loop total is bounded, not repeated. ---
def longest_run(arr):
    best, i = 0, 0
    while i < len(arr):                    # looks nested...
        j = i
        while j < len(arr) and arr[j] == arr[i]:
            j += 1                         # ...but j never moves backwards,
        best = max(best, j - i)            # so the inner loop advances a total
        i = j                              # of n times across the WHOLE run.
    return best                            # O(n)

# Sieve of Eratosthenes: the inner loop runs n/2 + n/3 + n/5 + ... times.
# That sum is n * (sum of reciprocals of primes < n) = O(n log log n).
def primes_up_to(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p <= n:                      # outer loop: O(sqrt(n)) values of p
        if is_prime[p]:
            for multiple in range(p * p, n + 1, p):   # n/p steps
                is_prime[multiple] = False
        p += 1
    return [i for i, prime in enumerate(is_prime) if prime]
                                           # total: O(n log log n), effectively linear

def merge_sort(arr):
    if len(arr) <= 1:                      # base case: O(1)
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])           # T(n/2)
    right = merge_sort(arr[mid:])          # T(n/2)
    return merge(left, right)              # O(n)

def merge(a, b):
    out, i, j = [], 0, 0
    while i < len(a) and j < len(b):       # each element moved exactly once
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    out.extend(a[i:]); out.extend(b[j:])
    return out                             # O(len(a) + len(b))

0 ≤ f(n) ≤ c · g(n)    for all n ≥ n₀

0 ≤ c · g(n) ≤ f(n)    for all n ≥ n₀

0 ≤ c₁ · g(n) ≤ f(n) ≤ c₂ · g(n)    for all n ≥ n₀

def get(arr, i):
    return arr[i]                          # address = base + i*size: O(1)

def is_even(n):
    return n % 2 == 0                      # O(1)

def binary_search(arr, target):
    """arr must be sorted. Halves the search range every iteration."""
    lo, hi = 0, len(arr) - 1
    while lo <= hi:                        # range: n, n/2, n/4, ... 1
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1                   # discard the whole lower half
        else:
            hi = mid - 1                   # discard the whole upper half
    return -1                              # O(log n) iterations

def maximum(arr):
    best = arr[0]
    for x in arr:                          # touches every element exactly once
        if x > best:
            best = x
    return best                            # O(n)

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))
    # log n levels of recursion x O(n) merging per level = O(n log n)

def bubble_sort(arr):
    """Compares every adjacent pair, repeatedly: O(n^2)."""
    a = list(arr)
    n = len(a)
    for i in range(n):                     # n passes
        swapped = False
        for j in range(n - i - 1):         #   up to n comparisons each
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:                    # early exit makes the BEST case O(n)
            break
    return a                               # worst and average: O(n^2)

def matrix_multiply(A, B):
    """Standard triple loop: O(n^3)."""
    n = len(A)
    C = [[0] * n for _ in range(n)]
    for i in range(n):                     # n
        for j in range(n):                 #   x n
            for k in range(n):             #     x n
                C[i][j] += A[i][k] * B[k][j]
    return C                               # O(n^3)

def all_subsets(items):
    """There are 2^n subsets, so merely listing them is O(2^n)."""
    result = [[]]
    for x in items:                        # each item doubles the result size
        result += [subset + [x] for subset in result]
    return result                          # O(2^n) time and O(2^n) space

def fib_naive(n):
    """Two recursive calls per level, depth n: about 2^n calls."""
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)   # O(2^n) — actually O(phi^n)

def permutations(items):
    """n! orderings; generating them all is O(n * n!)."""
    if len(items) <= 1:
        return [list(items)]
    out = []
    for i in range(len(items)):            # n choices for the first element
        rest = items[:i] + items[i + 1:]
        for p in permutations(rest):       #   x (n-1)! orderings of the rest
            out.append([items[i]] + p)
    return out                             # O(n!)

def tsp_bruteforce(dist):
    """Try every tour. n! candidates — correct, and hopeless past n ~ 11."""
    n = len(dist)
    best = float("inf")
    for order in permutations(list(range(1, n))):
        tour = [0] + order + [0]
        cost = sum(dist[tour[i]][tour[i + 1]] for i in range(len(tour) - 1))
        best = min(best, cost)
    return best

1 + 2 + 4 + 8 + ... + n/2 + n  <  2n   elements in total

class DynamicArray:
    """A dynamic array built on a fixed-size backing store, to show the
    resize that Python's list hides. Appends are O(1) amortized."""

    def __init__(self):
        self._capacity = 1
        self._size = 0
        self._data = [None] * self._capacity

    def append(self, x):
        if self._size == self._capacity:   # rare: happens log2(n) times overall
            self._resize(self._capacity * 2)
        self._data[self._size] = x         # common: O(1)
        self._size += 1

    def _resize(self, new_capacity):
        bigger = [None] * new_capacity     # O(n) allocation
        for i in range(self._size):        # O(n) copy
            bigger[i] = self._data[i]
        self._data = bigger
        self._capacity = new_capacity

    def __getitem__(self, i):
        if not 0 <= i < self._size:
            raise IndexError(i)
        return self._data[i]               # O(1) always

    def __len__(self):
        return self._size


a = DynamicArray()
for i in range(1000):                      # 1000 appends, ~10 resizes,
    a.append(i)                            # < 2000 element copies in total
assert len(a) == 1000 and a[999] == 999