Understanding log n complexity
Binary search, mergesort, quicksort, AVL Trees, Splay trees, B-trees and red-black trees, etc. are only some algorithms or data structures that $ log \, n $ is related to. But what does it mean, really? Can we think intuitively about it?
I believe one intuitive way of thinking about $ log \, n $ complexity is: How many times can $ n $ be divided in halves until reaching $ 1 $?
This is a good way to think about it, but let’s show why we can think of it that way. I’m aware of that there are many attempts for explaining this in an intuitive way out there, but I remember myself that I was not really satisfied until I got to the more mathematical way of seeing it.
Let's see how many times $ n $ can be divided until we reach $ 1 $.
$$ n / 2 $$ $$ \frac{\frac{n}{2}}{2} = \frac{n}{2} \cdot \frac{1}{2} = \frac{n}{2^2} $$ $$ \frac{n}{2^2} \cdot \frac{1}{2} = \frac{n}{2^3} $$ $$ \frac{n}{2^3} \cdot \frac{1}{2} = \frac{n}{2^4} $$ $$ \frac{n}{2^4} \cdot \frac{1}{2} = \frac{n}{2^5} $$ $$ \frac{n}{2^5} \cdot \frac{1}{2} = \frac{n}{2^6} $$ $$ ... $$ $$ \frac{n}{2^x} = 1 $$
Note: Dividing by $ 2 $ is the same as multiplying with its multiplicative inverse $ \frac{1}{2} $.
So we keep dividing by 2 until we get $ 1 $, where $ x $ is how many times we have divided. See how we're actually left with an equation, namely
$$ \frac{n}{2^x} = 1 \Leftrightarrow 2^x = n. $$
Recall from logarithms in your math class (if you need to refresh, read my post
about it) that this is an exponential equation that can be solved easily using the definitions of logarithms $$ 2^x = n \Rightarrow x = log_2 n $$
So what did we end up with? $ log \, n $, just what we wanted.
First I suggested an intuitive way of thinking about logarithms; how many times $ n $ could be divided in halves until reaching one. This is a really useful property, because it's used in computer science all the time when talking about trees (and other applications). For instance, the height of a complete binary tree is at most $ log_2 \, n $.
Then we saw how we could come up with this in a mathematical way.
Not really a long post, but it's pretty concrete. Ask any questions you might have in the comments field. =)
