O(log n) — logarithmic complexity

This is one of the most efficient complexities you can achieve in real tasks with large amounts of data.

Imagine we have a phone book with 1,000,000 names and we're looking for a specific one. Going linearly, we'd have to check every name, and that would take forever. But if we cut the array in half each time, discarding the half that definitely doesn't fit, we get binary search, and the result is found in ~20 steps. That's logarithmic efficiency.

This approach only works with sorted data. And it's at the heart of many search and optimisation algorithms.

Example: binary search in a sorted array

function binarySearch($array, $target) {
    $left = 0;
    $right = count($array) - 1;

    while ($left <= $right) {
        $middle = floor(($left + $right) / 2);
        if ($array[$middle] === $target) return $middle;

        if ($array[$middle] < $target) {
            $left = $middle + 1;
        } else {
            $right = $middle - 1;
        }
    }
    return -1;
}

Every step halves the search area. And instead of a million checks — just a few dozen. That's why O(log n) is as fast as it gets.

← Previous: O(n) — linear complexity · Whole series · Next: O(n log n) — linearithmic complexity →

First published in Ukrainian in the Telegram channel “Created to die” on June 22, 2025.