Algo: Logarithmic time

An algorithm is said to take logarithmic time if $T(n) = O(\log n)$. Due to the use of the binary numeral system by computers, the logarithm is frequently base $2$ (that is, $\log_2 n$, sometimes written $\lg n$). However, by the change of base equation for logarithms, $\log_a n$ and $\log_b n$ differ only by a constant multiplier, which in big-O notation is discarded; thus $O(\log n)$ is the standard notation for logarithmic time algorithms regardless of the base of the logarithm.

Algorithms taking logarithmic time are commonly found in operations on binary trees or when using binary search. A $O(\log n)$ algorithm is considered highly efficient, as the operations per instance required to complete decrease with each instance.