The motivation to write this article is twofold — partly from my own initial confusion in visualizing what logarithm means in the real world. And later while working with folks in the software engineering field, I found that many who have been in the industry for many many years have the same confusion. I can’t blame them — application of logarithms was never taught properly in school, at least in my experience. So here’s an attempt to help some of those who may be in the same boat I was in long ago.
Disclaimer: I am not attempting to “teach” logarithms here. I am only attempting to help you understand the application of logarithms, specifically to help understand the “cost” of traversing a binary tree, or in other words what does O(logN) mean. With this basic understanding of cost, I think one should be able to apply logarithmic calculations to other kinds of tree traversals and in general be able to visualize logarithms.
I’m going to break up this article into three parts. The first explains some basic concepts. The second part applies the concepts to a simple phone-directory-search usecase. The third part then represents the phone directory as a binary tree (just for kicks) and explains why the cost of traversing it can be O(logN).
PART 1
Basic concept 1: Let’s understand Logs — “What is the logarithm of a number”
School / Mathematical definition: A quantity representing the power to which a fixed number (the base) must be raised to produce a given number. In other words, the output of a log is the exponent of the base. Logarithm is powerful and it converts multiplication of inputs into addition of logs and makes huge calculations trivial. No arguments on that score.
With that definition, are you in a position to understand the following statement: The cost or order of complexity to find a node in a binary tree with N nodes is approximately O(logN)? Not everyone really understands this.
So, here is a very simple alternative answer.
“Log” of a number is “the number of times you need to divide that number by the ‘base’ to get an output equal to ‘1’”
(This above definition is also not helping much! I understand!! But trust me, by the end of this article, you may feel a bit more comfortable with applying logarithms!)
Example:
- log2(8) = 3. Divide 8 by 2 (the base). Do it 3 times and you get ‘1’
- Log10(10000) = 4. Divide 10000 by 10 (the base). Do it 4 times and you get ‘1’
It’s just another way of saying it. But makes the understanding of logs trivial I think.
So again, lets not talk about “exponent”. Lets talk division. Its easier to understand. Keep this basic concept in mind and lets move to the next basic concept.
Basic Concept 2: Let’s understand why multiplying or dividing something by 2 is so important in computer science
Computers have always used the concept of representing information using “off” and “on” states. Numerically this can be represented using 0’s and 1’s respectively. So in computers and digital electronics 0 and 1 is all we have to express anything — and everything! Alphabets, special characters, numbers, decimals, images, videos — everything is expressed using 0’s and 1’s. And a number system with only 0’s and 1’s is called a binary system. Its a system using base “2”. That is why 2 is important.
And, as humans, one of the things we are very good at understanding is the concept of “doubling” something or “halving” something. This aspect is again using base “2” system.
Keeping the above in mind, lets start working with a number called “N”. N is any arbitrary positive whole number (e.g. 1, 2, 36, 777, 100000 etc.)
Now lets mix N with “2”. N times 2 can be represented as Nx2. And what we just did is we doubled “N”. If we want to double the above again then we will write — Nx2x2 = Nx2²
So every time we multiply a number by 2 we are doubling it. Extrapolating this concept, then, what is Nx2¹⁰. It is “doubling N, 10 times”. That is what “Nx2¹⁰” means. (Note: For “fast readers”, just to reemphasize, “Nx2¹⁰” is NOT 10 times N. <grin>)
Lets go the other way. What does N/2 mean? It means we are dividing N by 2 = “half”. How is half of half of N represented numerically? N/2². Easy peasy!
Now try this: what does the following mean: N divided by 2¹⁰? Written mathematically: N / 2¹⁰?
If you said, it means you are halving N, 10 times, you are keeping up!
PART 2
Now lets apply the above “basic concept 2” to a usecase from the 1990s
Let’s go back to the 1990s. Let’s say you owned a telephone directory (a book containing an index of names with associated phone numbers) and let’s say it contained 512 pages. You need to look up the phone number of “Turing”. What will you do?
Answer:
You will open to the middle of the book and see if you found Turing on that page. If your phone book was printed correctly, chances are, you would not. Names starting with “T” will be printed in the 2nd half of the book. So, you now start looking in the 2nd half of the book. (side note: we just said 2nd →“2”)
You will now divide the 2nd half into 2 again. And check if “T” is in the first part of the 2nd half or the 2nd part of the 2nd half. viz: again divide this part into half (divide by 2). You do this till you get to that ONE page on which the phone number for Turing exists.
We said, we have 512 pages in the book. For a second, lets say, you are a super busy genius who has employed a robot to find you the phone number of Turing. How many times will your robot divide the 512 page book by half to get you to that ‘1’ page which had Turing written on it? The maximum times the robot would have done it is the “number of times you would divide 512 by 2 till you get ‘1’”.
512/2 = 256; 256/2 = 128; 128/2 = 64; 32.. ; 16.. ; 8.. ; 4.. ; 2.. ; 1!
Not sure if you noticed above, but you had to divide 512 by 2, 9 times, before you got to 1. That is the maximum number of times your robot would have flipped pages. It could have found the number in less than 9 times. But for sure, if it happened to be more than 9 times, then mostly your robot was a defective piece of machinery and you can have my sympathies for owning such a robot.
Come logarithm… lets apply basic concept 1 from above
What tool do we have to quickly calculate “how many times” we need to divide by 2 to get to “1”? The answer is “log to the base 2” or “log2”.
log2(512) = 9!!
In this article this was the first time we applied logarithm to a real world problem!
PART 3
Lets now fast forward to “Binary Trees”
Lets represent our search in the form of a Binary Tree. A binary tree is a tree structure (see below) whose elements have at most 2 children. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.
The tree below shows us what your robot just did. Starting with the top level node which is the entire phone book, it kept going to the center page one half after another to get to the page that has all names starting with “Tu”.
As you can see above (and this example is of course tailored to find the name “Turing” in 9 steps), we keep dividing up the pages in the book into into left half and right halves as we go to that “1” page which has all names starting with “Tu” and hence we find “Turing” on that final page. We go from 512 pages to “1” page in 9 steps.
Log2(512) = 9. And it means keep dividing by 2, “9” times till you get “1” — the final page.
Did you understand how we “applied” logarithm to get you an estimate of number of steps you took to get to the name you were searching for?
So if your book now had 1000 pages, approximately how many steps would you need to take to find the same name “Turing” in that book? The answer is:
Log2(1000) ~= 10. Note 2¹⁰ = 1024. You would divide the book by half 10 times (maximum) to find the name you were looking for.
Do you also see you just added another ~500 pages to your book (512 -> 1000) and in spite of that, you just had to take ONE additional step ( 9 -> 10) to find the name “Turing”?!! That is the power of Trees!
Cost: The “cost” or number of operations the computer would execute for you is 10 in the above example. That is what is represented by “Order of complexity”. And in this case therefore we will call it O(Log2(1000)). And to make it generic we go back to our friend, “N”. We call it O(Log2(N)), where “N” represents the total number of nodes (pages in our example) that you will need to represent your problem statement.
Side Note: If you look at the tree above, the number of paths from the top node (root) to the bottom-most node (Tu) or “leaf” node is 9. This is called the “height” of the tree. In other words, Log2(N) for a binary tree = “height” of the tree.
Hope this article helped you to understand logarithms and as they apply to binary trees. Let me know if you have any inputs or questions.
