Logarithmic time

An algorithm is said to take logarithmic time when T(n) = O(log n). Since log_a n and log_b n are related by a constant multiplier, and such a multiplier is irrelevant to big-O classification, the standard usage for logarithmic-time algorithms is O(log n) regardless of the base of the logarithm appearing in the expression of T.

Algorithms taking logarithmic time are commonly found in operations on binary trees or when using binary search.

An O(log n) algorithm is considered highly efficient, as the ratio of the number of operations to the size of the input decreases and tends to zero when n increases. An algorithm that must access all elements of its input cannot take logarithmic time, as the time taken for reading an input of size n is of the order of n.

An example of logarithmic time is given by dictionary search. Consider a dictionary D which contains n entries, sorted by alphabetical order. We suppose that, for 1 ≤ k ≤ n, one may access the kth entry of the dictionary in a constant time. Let D(k) denote this k-th entry. Under these hypotheses, the test to see if a word w is in the dictionary may be done in logarithmic time: consider ${\displaystyle D(\lfloor <!--\; \lfloor \; -->n/2\rfloor <!--\; \rfloor \; -->),}$ where ${\displaystyle \lfloor <!--\; \lfloor \; -->\rfloor <!--\; \rfloor \; -->}$ denotes the floor function. If ${\displaystyle w=D(\lfloor <!--\; \lfloor \; -->n/2\rfloor <!--\; \rfloor \; -->),}$ then we are done. Else, if continue the search in the same way in the left half of the dictionary, otherwise continue similarly with the right half of the dictionary. This algorithm is similar to the method often used to find an entry in a paper dictionary.