Where does log (n) get into O (N) notation

Question

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

• O (n) means I have to go through the sequence after
• O (n ² ) means that I have two sequences of nested loops intersecting the sequence

But how do I get log (N)?

PS: I know the collection APIs and some classes that have O (n log n) traversal times. I need a simple explanation.

Answer 1

lg N occurs in separation and rest algorithms, where you iteratively or recursively skip half the data in a collection of N elements. Binary search is a typical example. Insert, search, and delete operations in binary search trees are also O (log N).

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

Array sorting can be done in O (N lg N) using algorithms such as mergesort, but also conceptually simpler: iterating through the array and placing elements in a binary search tree. Each insert takes O (log N) and their N, so the algorithm works in O (N log N).

(BST sorting even has worse O (N log N) complexity if the tree is balanced .)

Answer 2

The best example of N * log (N) , in my opinion, would be to search for a comparison based search:

Let's take merge-sort as an example.

The algorithm takes an array of elements, splits it into 2 recursively, until it gets an array of length 2, and then combines the parts in O (n), each merging of sorted arrays is easier.

Ok, that was a short description, now let's see what it looks like:

[ 1 2 3 4 5 6 7 8 ] | /\ [1 2 3 4] [ 5 6 7 8 ] | | /\ /\ [1 2 ] [ 3 4] [5 6] [7 8] 

I hope you can see here that the recursion depth is log (n) (because it is a tree that has 2 branches ... so log (n) with base 2)
But at every level of the tree, there are O (n) operations (because we are actively rebuilding the n object).

So here N * log (N) is complicated.

Most algorithms that have Log (N) complexity get this from the tree algorithm.
There are a few that are just probabilistic log (n) (which means that after a long mathematical calculation you get that on average it will be something like log (n))

Answer 3

A typical algorithm with O (log n) complexity is a binary search in a sorted array. Instead of passing through each element one O(n) , you iteratively split the array in half and look only at half where you know what your element may be.