take logarithmic time, as the time taken for reading an input of size is of the order of .

An example of logarithmic time is given by dictionary search. Consider a dictionary which contains entries, sorted in alphabetical order. We suppose that, for , one may access the th entry of the dictionary in a constant time. Let denote this th entry. Under these hypotheses, the test to see if a word is in the dictionary may be done in logarithmic