O(log n)

O(log n): Logarithmic Time

Logarithm là phép toán nghịch đảo của lũy thừa: - log₁₀(1000) = 3 vì 10³ = 1000 - log₂(8) = 3 vì 2³ = 8

Đặc điểm

• Thời gian tăng rất chậm theo kích thước đầu vào
• Hiệu suất rất tốt cho dữ liệu lớn

Ví dụ: Binary Search (Tìm kiếm nhị phân)

function binarySearch(arr, target) {
    let left = 0;
    let 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;
}

Tại sao hiệu quả?

• Mỗi bước loại bỏ một nửa không gian tìm kiếm
• Với mảng 1000 phần tử → chỉ cần tối đa 10 bước so sánh