In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, logarithmic growth describes a phenomenon whose size or cost can be described as a logarithm

Logarithm

The logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...

 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 a fixed constant. Logarithmic growth is the inverse of exponential growth

Exponential growth

Exponential growth occurs when the growth rate of a mathematical function is proportional to the function's current value...

 and is very slow.

A familiar example of logarithmic growth is the number of digits needed to represent a number, N, in positional notation

Positional notation

Positional notation or place-value notation is a method of representing or encoding numbers. Positional notation is distinguished from other notations for its use of the same symbol for the different orders of magnitude...

, which grows as log_b (N), where b is the base of the number system used, e.g. 10 for decimal arithmetic. Another example is in cryptography

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, where the key

Key (cryptography)

In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...

 size needed to protect against a brute force attack

Brute force attack

In cryptography, a brute-force attack, or exhaustive key search, is a strategy that can, in theory, be used against any encrypted data. Such an attack might be utilized when it is not possible to take advantage of other weaknesses in an encryption system that would make the task easier...

 for a certain period of time grows logarithmically with the desired protection interval.

In the design of computer algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

s, logarithmic growth, and related variants, such as log-linear, or linearithmic, growth are very desirable indications of efficiency.

Logarithmic growth can lead to apparent paradoxes, as in the martingale roulette system, where the potential winnings before bankruptcy grow as the logarithm of the gambler's bankroll. It also plays a role in the St. Petersburg paradox

St. Petersburg paradox

In economics, the St. Petersburg paradox is a paradox related to probability theory and decision theory. It is based on a particular lottery game that leads to a random variable with infinite expected value, i.e., infinite expected payoff, but would nevertheless be considered to be worth only a...

.

In microbiology

Microbiology

Microbiology is the study of microorganisms, which are defined as any microscopic organism that comprises either a single cell , cell clusters or no cell at all . This includes eukaryotes, such as fungi and protists, and prokaryotes...

, the rapidly growing exponential growth phase of a cell culture

Cell culture

Cell culture is the complex process by which cells are grown under controlled conditions. In practice, the term "cell culture" has come to refer to the culturing of cells derived from singlecellular eukaryotes, especially animal cells. However, there are also cultures of plants, fungi and microbes,...

 is sometimes called logarithmic growth. During this bacterial growth

Bacterial growth

250px|right|thumb|Growth is shown as L = log where numbers is the number of colony forming units per ml, versus T Bacterial growth is the division of one bacterium into two daughter cells in a process called binary fission. Providing no mutational event occurs the resulting daughter cells are...

 phase, the number of new cells appearing are proportional to the population.

See also

• Iterated logarithm
  Iterated logarithm
  In computer science, the iterated logarithm of n, written  n , is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1...
  
  - an even slower growth model