In
mathematics, logarithmic growth describes a phenomenon whose size or cost can be described as a
logarithm
In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number to the base is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 of ...
function of some input. e.g. ''y'' = ''C'' log (''x''). Note that any logarithm base can be used, since one can be converted to another by multiplying by a fixed constant.
[.] Logarithmic growth is the inverse of
exponential growth
Exponential growth is a process that increases quantity over time. It occurs when the instantaneous rate of change (that is, the derivative) of a quantity with respect to time is proportional to the quantity itself. Described as a function, a ...
and is very slow.
A familiar example of logarithmic growth is a number, ''N'', in
positional notation, which grows as log
''b'' (''N''), where ''b'' is the base of the number system used, e.g. 10 for decimal arithmetic. In more advanced mathematics, the
partial sums of the
harmonic series
:
grow logarithmically. In the design of computer
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s, logarithmic growth, and related variants, such as log-linear, or
linearithmic
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
, growth are very desirable indications of efficiency, and occur in the
time complexity
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
analysis of algorithms such as
binary search
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the posi