Explain what the complexity of an algorithm O(log n) means and in what cases it is used.

An algorithm with a complexity of O(log n) means that the execution time grows proportionally to the logarithm of the input size. This means that when the volume of data increases several times, the number of operations increases not linearly, but much more slowly.

Such complexity is characteristic of algorithms that reduce the problem size by about half at each step. For example:

• Binary search in a sorted array — at each step, half of the elements are discarded.
• Some algorithms working with trees (for example, search in a balanced binary tree).

Example of binary search in Java:

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

Here, the number of search steps grows approximately as log₂(n), where n is the size of the array.