What does Log N complexity actually entail?

Question

I know what log n complexity usually entails in practice (binary search, looking up a person in a phone book and breaking it down smaller and smaller instead of going through A to Z, divide and conquer) but I'm still not sure from a mathematical/computational standpoint what and why a certain process is said to have a time complexity of log n.

Answer 1

I suggest you read up on big O notation on other websites that explain it well, instead of asking on StackOverflow.

Disclaimer this is very simplified explanation, for general explanation you should look into big O definition.

As for why is binary search O(log n). It boils down to the number of operations you perform. For arrays of lengths you need to perform:

len: 0, ops: 1
len: 1, ops: 1
len: 2, ops: 2
len: 3, ops: 2
len: 4, ops: 3
len: 5, ops: 3
len: 6, ops: 3
len: 7, ops: 3
len: 8, ops: 4
...
len: 16, ops: 5
...

In each iteration you can perform 1 operation and repeat the binary search on array with lenght half the size. That's where the logarithm comes from. For array of length 2^n, you need at most log_2 n operations.

Answer 2

One clear example of log(n) complexity is traversing a rooted tree from root to one of its leaf (like binary search as you've mentioned). If you have n objects from which you want to create a balanced rooted tree, the height of this tree will be log(n). Because a binary balanced tree has 2^h nodes in maximum (h is the height of the tree), and if you solve n = 2^h, you will find that height of the tree, h, should be log(n).

In sum, most of the time in regular algorithms, the provenance of log(n) in complexity comes from the traversing a balanced rooted tree (or generally a rooted tree), from its root to one of its leaf in a top-down approach.