My mathematical education was somewhat lacking as at school I was put in the "divvy" classes - classes for the "not too bright" or "remedial". So coming across terms like "logarithm" is a little unsettling. I'm assuming that some people reading this may not be familiar with the term either, so I will endeavour to understand it myself and explain it. So what is a logarithm?
Doing a search on the Googles for "what is a logarithm" it comes up with this:
a quantity representing the power to which a fixed number (the base) must be raised to produce a given number
(As an aside, the derivation of "logarithm" is from the Greek 'logos', meaning 'reckoning, ratio', and 'arithmos' meaning 'number').
That is a pretty meaty sentence so I had to do some more searching. I would recommend going to Khan academy and watching this cool video on Logarithms. To put that grounding into use I started applying it with binary trees. I think they are a good example to start with, as binary has only two options, making you choose one (true or false?). So you can either visit binary algorithms on wikipedia or not! I used this log calculator too as it is pretty simple, reminds me of Richard Feynman (I love Richard Feynman) here my girlfriend is rolling her eyes.
Anyhoo, just to set the foundation, the logarithm of 4 with a base of 2 is 2. The base is 2 in this instance as we are using a binary tree. So we would write it like Log2(4) = 2. A point to note about this, is that Log2(4) = 2 is the same as 22 = 4. So using a binary tree this means it will take a maximum of 2 steps to get to the deepest node (starting with 1, obviously).
It looks like we only need to include only one of the deepest nodes in our calculation. That makes sense because adding more nodes at the same depth will have no bearing on the number of operations.
The logarithm of 8 is 3. Log2(8) = 3 is the same as 23 = 8. You should notice that it takes a maximum of 3 operations to access the deepest node.
The logarithm of 16 is 4. Log2(16) = 4 is the same as 24 = 16. And so on. (the numbers below are random)
Another way to look at it is that the log of n correlates to the depth of the tree. I've come to realise that Mathematics is about seeing patterns in things.
Algorithms that use O(log n) are extremely fast because adding more and more branches only increases the number of operations by log 2 of n. This is like the classic example of searching for a name in a telephone book.
Another good description of O(log n) I came across, is on stack overflow called What does O(log n) mean exactly?.
This is all simple stuff once it clicks or is explained well.