Logarithmic time complexity describes algorithms in which the number of operations grows proportionally to the logarithm of the input size. A common way to obtain logarithmic complexity is to reduce the remaining problem by a fixed fraction at each step. For example, binary search examines the middle element of a sorted array and discards approximately half of the remaining elements after each comparison. If an array contains 1,024 elements, repeated halving reduces the search range to approximately one element after ten reductions because 2¹⁰ = 1,024. Thus, the number of steps grows slowly compared with the original input size. Logarithmic complexity also appears in balanced binary search trees, binary heaps, and algorithms that repeatedly double or halve a quantity. The base of the logarithm does not affect the asymptotic class when it is a constant greater than one, because logarithms with different constant bases differ only by a constant multiplier. However, the algorithm must satisfy the conditions that produce logarithmic behavior. Binary search, for example, requires sorted data and a suitable random-access structure for its standard O(log n) analysis. An algorithm that removes only one element per step is generally not logarithmic, even if it uses a loop.
Logarithmic Time Complexity — O(log n)
Logarithmic time complexity occurs when an algorithm repeatedly reduces the remaining problem size by a constant factor.
T(n) ∈ O(log_b n), where b > 1 is a constant reduction factor.
Explanation
Variables
| Symbol | Meaning | Unit |
|---|---|---|
n | Initial input size. | Number of elements or problem units |
b | Constant factor by which the remaining problem size is reduced. | Dimensionless constant |
T(n) | Number of operations required for input size n. | Operations |
Example or application
Binary search begins with 1,024 sorted elements. Each comparison reduces the search range to approximately half: 1,024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1. This requires about 10 reductions, so the number of steps grows logarithmically with n.
Key Properties
The number of operations grows logarithmically with input size.
Repeatedly dividing the problem by a constant factor often produces O(log n).
The logarithm's constant base does not change its asymptotic class.
Logarithmic growth is much slower than linear growth for sufficiently large inputs.
Binary search is a standard example.
The data structure and problem conditions can determine whether logarithmic performance is possible.
Prerequisites
Understanding of loops and input size.
Basic logarithms and exponents.
Basic understanding of sorted arrays.
Learning Objectives
Explain why repeated halving produces logarithmic complexity.
Recognize algorithms with logarithmic growth.
Estimate the number of reductions for a given input size.
Identify the assumptions required by binary search.
Core Concepts
Logarithm
Repeated halving
Constant-factor reduction
Binary search
Balanced search structures
Growth rate
Step By Step
Identify the initial problem size n.
Determine how much of the problem remains after each step.
Check whether the remaining size is reduced by a constant factor.
Express the number of reductions using a logarithm.
Classify the running time as logarithmic when each step takes constant work.
Pseudocode
ALGORITHM BinarySearch(A, target)
low = 0
high = length(A) - 1
WHILE low <= high
mid = floor((low + high) / 2)
IF A[mid] = target
RETURN mid
ELSE IF A[mid] < target
low = mid + 1
ELSE
high = mid - 1
END IF
END WHILE
RETURN NOT_FOUND
Complexity
Time
O(log n)
Space
O(1)
Explanation
Each iteration discards approximately half of the remaining search range. The iterative implementation uses a fixed number of additional variables.
Applications
Binary search in sorted arrays.
Searching in balanced binary search trees.
Insertion and deletion in balanced search trees.
Operations in binary heaps.
Repeated doubling or halving calculations.
Efficient search over ordered numeric ranges.
Common Mistakes
Using binary search on unsorted data.
Assuming every algorithm with repeated steps is logarithmic.
Confusing logarithmic growth with linear growth.
Ignoring the cost of work performed during each reduction.
Assuming that a linked-list implementation provides the same binary-search performance as an array.
Key Takeaways
O(log n) commonly results from repeatedly reducing a problem by a constant factor.
Binary search is a classic logarithmic-time algorithm.
Logarithmic algorithms scale efficiently to large inputs.
The conditions of the algorithm and the underlying data structure matter.
Related Topics
Constant Time Complexity
Linear Time Complexity
Binary Search
Balanced Binary Search Trees
Complexity Comparison and Growth Rates
Limitations
The suitability of logarithmic time complexity — o(log n) depends on the exact problem requirements and the assumptions made about the input.
An implementation of logarithmic time complexity — o(log n) can fail if its boundary conditions, data representation, or required invariants are handled incorrectly.
For logarithmic time complexity — o(log n), evaluate representative and unusually difficult inputs; a single small demonstration is not enough to establish reliability.
Practice Questions
| Question | Answer |
|---|---|
What is the main purpose of logarithmic time complexity — o(log n)? | Logarithmic time complexity occurs when an algorithm repeatedly reduces the remaining problem size by a constant factor. |
What should be checked before applying logarithmic time complexity — o(log n)? | For logarithmic time complexity — o(log n), verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of logarithmic time complexity — o(log n) be validated? | Trace a representative logarithmic time complexity — o(log n) case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- SCIENEXY Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures