VietMX Staff asked 3 years ago
O(log n) means for every element, you’re doing something that only needs to look at log N of the elements. This is usually because you know something about the elements that let you make an efficient choice (for example to reduce a search space). The most common attributes of logarithmic running-time function are that:
- the choice of the next element on which to perform some action is one of several possibilities, and
- only one will need to be chosen
or
- the elements on which the action is performed are digits of
n
Most efficient sorts are an example of this, such as merge sort. It is O(log n) when we do divide and conquer type of algorithms e.g binary search. Another example is quick sort where each time we divide the array into two parts and each time it takes O(N) time to find a pivot element. Hence it N O(log N)
Plotting log(n) on a plain piece of paper, will result in a graph where the rise of the curve decelerates as n increases:
