Editing Time complexity (section)

== Logarithmic time ==
{{Further|Logarithmic growth}}
An algorithm is said to take '''logarithmic time''' when <math>T(n) = O(\log n)</math>.  Since <math>\log_a n</math> and <math>\log_b n</math> are related by a [[Logarithmic identities#Changing the base|constant multiplier]], and such a [[Big O notation#Multiplication by a constant|multiplier is irrelevant]] to big O classification, the standard usage for logarithmic-time algorithms is <math>O(\log n)</math> regardless of the base of the logarithm appearing in the expression of {{mvar|T}}.

Algorithms taking logarithmic time are commonly found in operations on [[binary tree]]s or when using [[binary search]].

An <math>O(\log n)</math> 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 {{mvar|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 {{mvar|n}} is of the order of {{mvar|n}}.

An example of logarithmic time is given by dictionary search. Consider a [[Dictionary (data structure)|dictionary]] {{math|''D''}} which contains {{mvar|n}} entries, sorted in [[alphabetical order]]. We suppose that, for <math>1 \le k \le n</math>, one may access the {{mvar|k}}th entry of the dictionary in a constant time. Let <math>D(k)</math> denote this {{mvar|k}}th entry. Under these hypotheses, the test to see if a word {{mvar|w}} is in the dictionary may be done in logarithmic time: consider <math>D\left(\left\lfloor \frac{n}{2} \right\rfloor\right)</math>, where <math>\lfloor\;\rfloor</math> denotes the [[floor function]]. If <math>w = D\left(\left\lfloor \frac{n}{2} \right\rfloor\right)</math>--that is to say, the word {{mvar|w}} is exactly in the middle of the dictionary--then we are done. Else, if <math>w < D\left(\left\lfloor \frac{n}{2} \right\rfloor\right)</math>--i.e., if the word {{mvar|w}} comes earlier in alphabetical order than the middle word of the whole dictionary--we continue the search in the same way in the left (i.e. earlier) half of the dictionary, and then again repeatedly until the correct word is found. Otherwise, if it comes after the middle word, 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. As a result, the search space within the dictionary decreases as the algorithm gets closer to the target word.