Logarithmic time complexity

As explained in 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)).

Logarithmic time complexity describes work that grows with the logarithm of the number of elements, commonly written O(log(n)). A balanced binary search tree reaches a target by choosing only one branch at each comparison, so doubling the elements requires only about one additional set of comparisons. section 7.2.1

Searching a map

To find key 2 in a balanced tree containing 1, 3, and 5, begin at 3, move left to 1, and stop when the search path ends. An std::map commonly uses this structure, giving search, insertion, and removal logarithmic complexity. By contrast, searching a vector is O(n): in the worst case, every element must be checked. section 7.2.1 section 7.4

Figure 7.2 Three elements in a balanced binary search tree: nodes with smaller keys go on the left and larger keys on the right.

See how smaller keys occupy the left branch and larger keys the right branch in a balanced binary search tree. section 7.2.1

How Learn C++ by Example covers it

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.

How it connects

Connects logarithmic complexity to std::map, balanced binary search trees, red-black trees, vectors, and linear complexity.

liveBookmanning.com

Read Learn C++ by Example on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Advanced Algorithms and Data StructuresLogarithmic time is a running-time bound that grows proportionally to the logarithm of the input size or another stated size parameter.
• 

  liveBookmanning.com
  Grokking Algorithms, Second EditionLogarithmic time describes an algorithmic running time that grows in proportion to the logarithm of the input size.
• 

  liveBookmanning.com
  LatencyLogarithmic time is an algorithmic growth class in which required operations increase proportionally to the logarithm of input size.

Compare how 4 books explain logarithmic time complexity →

Related concepts

• linear time complexitycontrasts with · Linear time complexity is an asymptotic running-time growth rate proportional to input size, or to the combined sizes of multiple inputs, up to a constant factor.
• binary searchmeasured by · Binary search is an algorithm that locates a target or boundary in an ordered collection by repeatedly comparing with a midpoint and halving the remaining search range.
• performancemeasured by · Performance is the measurable effectiveness or operational behavior of a system under specified conditions, assessed through relevant qualities such as task results, speed, responsiveness, throughput, or resource use.
• insertmeasures · An insertion is an operation that adds an element, record, or key-value association to a collection or data store, with placement and replacement behavior determined by the target.
• execution context stackmeasures · An execution context stack is a runtime last-in-first-out structure that records active function or method calls and their execution state and return information.
• AVL treemeasures · An AVL tree is a self-balancing binary search tree that maintains bounded differences between subtree heights through rotations.

This explainer was generated by Manning's knowledge graph from the text of Learn C++ by Example. The section links point to the parts of the book it draws on.