liveBook · Manning

Logarithmic time complexity

As explained in Algorithms Every Programmer Should Know

Logarithmic time is a complexity class whose execution time grows in proportion to the logarithm of input size.

Logarithmic time describes runtime growth in relation to input size. Binary search illustrates it: on a sorted array, check the middle value and choose the half that could contain the target. section 1.3.1

Searching by halves

Compare the target with the middle value. If they differ, continue in the half where the target could be; repeat, eliminating half the remaining array each time. This takes O(log N), compared with O(N) for checking entries one by one. section 1.3.1

Figure 1.1 List of categories of time complexity used in algorithm analysis, including constant time O(1), linear time O(N), quadratic time O(N^2), and logarithmic time O(logN). N represents the increasing input size, highlighting the performance differences in time complexities.

Compare logarithmic growth with constant, linear, and quadratic time as input size increases. section 1.3.1

How Algorithms Every Programmer Should Know covers it

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 it assumes
Explains input size N and time complexity through examples; uses a sorted array for binary search.
What you can do after
Understand how repeatedly halving a search space yields O(log N) runtime.
How it connects
Connects logarithmic time to binary search, sorted arrays, and time complexity.

Also explained in

Compare how 5 books explain logarithmic time complexity →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.