Что такое logn

Логарифмическая сложность O(log n) означает, что время выполнения алгоритма растёт пропорционально логарифму от размера входных данных. Часто встречается в алгоритмах, которые на каждом шаге делят задачу пополам.

Пример - бинарный поиск:

int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Здесь на каждой итерации поисковое пространство уменьшается вдвое, что даёт сложность O(log n).