Where does log(n) come from in the O(N) notation

Question

I know what is O(n) notation and I also understand how I can get notations like O(n), O(n²), ....

• O(n) means I have to get through sequence once
• O(n²) means that I have two nested cycles traversing sequence

But how do I get log(N)?

P.S.: I know the Collections API and some classes that have O(n log n) traversal time. I need a simple explanation.

Answer 1

lg N comes about in divide-and-conquer algorithms, where you iteratively or recursively skip half of the data in a collection of N items. Binary search is the quintessential example. The insert, lookup and delete operations on binary search trees are also O(lg N).

Iteratively discarding half the elements is, in an intuitive sense, the inverse of iteratively doubling the number of elements. Doubling would produce O(2^N) elements in N iterations. Note that the binary logarithm of N is the inverse of raising two to the power N.

Sorting an array can be done in O(N lg N) by algorithms such as mergesort, but also conceptually simpler: iterate over the array and put the elements in a binary search tree. Each insert takes O(lg N) and there are N of them, so the algorithm runs in O(N lg N).

(The sort-by-BST even has worst-case O(N lg N) complexity if the tree is balanced.)