Logarithmic time complexity
An algorithmic running-time growth rate proportional to the logarithm of the input size, commonly expressed as O(log n).
Advanced Algorithms and Data Structures
Logarithmic time is a running-time bound that grows proportionally to the logarithm of the input size or another stated size parameter.
- How it is used
- Guides data-structure selection when partial ordering, heap operations, or balanced-tree access should scale beyond linear scans.
- How deep it goes
- Explains height and comparison bounds, worst-case versus amortized guarantees, logarithm bases, and practical constant-factor trade-offs.
- Examples
- Uses task-priority insertion, binary-heap comparisons, cache performance tables, and balanced k-d-tree construction.
- What you can do after
- Evaluate data structures by separating asymptotic growth, balance assumptions, worst-case guarantees, amortization, and implementation constants.
Read how Advanced Algorithms and Data Structures explains logarithmic time complexity →
Grokking Algorithms, Second Edition
Logarithmic time describes an algorithmic running time that grows in proportion to the logarithm of the input size.
- How it is used
- Compares algorithm growth rates and highlights why binary search scales better than simple search.
- How deep it goes
- Explains logarithmic growth through examples and comparisons, while simplifying operation counts and deferring fuller Big O treatment.
- Examples
- Uses binary-search guesses, folded grids, operation counts, and quicksort call stacks as concrete examples.
- What you can do after
- Evaluate whether an algorithm grows logarithmically and compare its scaling with linear and other common runtimes.
Read how Grokking Algorithms, Second Edition explains logarithmic time complexity →
Learn C++ by Example
Logarithmic complexity is an algorithmic growth rate proportional to the logarithm of the number of input elements, commonly expressed as O(log(n)).
- How it is used
- Explains why ordered associative containers keep searches, insertions, and removals efficient.
- How deep it goes
- Explains branch-by-branch search, doubling behavior, and tree balancing, but does not derive logarithms mathematically.
- Examples
- Uses a three-node search path and contrasts map lookup with worst-case vector scanning.
- What you can do after
- Evaluate data-structure choices by comparing logarithmic map operations with linear vector searches.
Read how Learn C++ by Example explains logarithmic time complexity →
Algorithms Every Programmer Should Know
Logarithmic time is a complexity class whose execution time grows in proportion to the logarithm of input size.
- How it is used
- Measures how algorithm runtime changes as input size grows, using binary search to illustrate a search strategy.
- How deep it goes
- Explains binary search's repeated halving and identifies its runtime as O(log N).
- Examples
- Uses binary search for a target in a sorted array and contrasts it with linear scanning.
- What you can do after
- Understand how repeatedly halving a search space yields O(log N) runtime.
Read how Algorithms Every Programmer Should Know explains logarithmic time complexity →
Latency
Logarithmic time is an algorithmic growth class in which required operations increase proportionally to the logarithm of input size.
- How it is used
- Compares algorithmic growth to guide work elimination and low-latency optimization.
- How deep it goes
- Defines growth behavior and trade-offs, then shows data-structure cases without deriving logarithmic operations internally.
- Examples
- Uses a complexity-growth figure and binary search tree operation table to compare logarithmic, linear, quadratic, and constant growth.
- What you can do after
- Evaluate algorithm choices by comparing asymptotic growth with input size, execution frequency, and absolute latency.
Also covered in
What to know first
- arrayAn array is an ordered collection of elements organized in one or more dimensions and accessible by position or index.
- binary searchBinary search is an algorithm that repeatedly halves an ordered search interval to locate a target or determine its position or boundary.
- performancePerformance is a measure of how effectively a person, process, model, or system achieves its objectives, including qualities such as output quality, speed, and resource efficiency.
- vectorA vector is an ordered sequence of elements treated as a single object, with its size fixed or resizable depending on the context.
Related concepts
- time complexitykind of · Time complexity describes how an algorithm’s execution time grows as a function of its input size or parameters.
- linear time complexitycontrasts with · Linear time complexity is an asymptotic running-time bound that grows at most proportionally to the input size, or combined input sizes, ignoring constant factors.
- binary searchmeasured by · Binary search is an algorithm that repeatedly halves an ordered search interval to locate a target or determine its position or boundary.
- AVL treemeasures · An AVL tree is a self-balancing binary search tree that maintains bounded differences between subtree heights through rotations.
- call stackmeasures · A call stack is a runtime LIFO structure that tracks active function or method calls, including their execution contexts and return information.
- insertmeasures · Insertion is an operation that adds an element, record, or value to a data structure or data store.
Questions about logarithmic time complexity
What is logarithmic time complexity?
An algorithmic running-time growth rate proportional to the logarithm of the input size, commonly expressed as O(log n).
Which Manning books explain logarithmic time complexity?
Advanced Algorithms and Data Structures, Grokking Algorithms, Second Edition, Learn C++ by Example, Algorithms Every Programmer Should Know and Latency.
What should I know before learning logarithmic time complexity?
Manning books that teach logarithmic time complexity usually introduce array, binary search, performance and vector first.
What is the difference between logarithmic time complexity and linear time complexity?
An algorithmic running-time growth rate proportional to the logarithm of the input size, commonly expressed as O(log n). Linear time complexity is an asymptotic running-time bound that grows at most proportionally to the input size, or combined input sizes, ignoring constant factors.
What is logarithmic time complexity a kind of?
Logarithmic time complexity is a kind of time complexity. Time complexity describes how an algorithm’s execution time grows as a function of its input size or parameters.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.




