What is a logarithm?

If you type the definition of logarithm in Google, it spits out something unhelpful, like:

a quantity representing the power to which a fixed number (the base) must be raised to produce a given number.

Don't blame yourself if you struggle with remembering it.

The fact is, nobody in Computer Science thinks of logarithm like that.

So, how do they think about it?

Well, as a tree height...

Don't kill me. Let me explain.

What tree are we talking about?

Are Computer Scientists insane? No. We are just imaginitive.

Binary search tree

We can think of sorted array as a tree. Every element of an array is a node. Middle of the array is the root. Then all the elements left to the node is smaller than it. Every element to the right of the node is larger than it.

Every node has at most two children.

Nodes that have no children, we would call leaves.

For example, sorted array [1, 3, 4, 5, 6, 7, 7, 8, 23, 55, 80, 111, 300, 901] in the tree form could look like this:

Does it look like a tree to you? Well, it's upside down, to begin with. But you can see root, branches, leaves - now you can see the tree!

In fact, as long as we follow the rule "all to the left - smaller, all to the right - larger", even this construction could call itself a tree:

This one, is, in fact, unbalanced.

Let's look at the height of this tree.

Height of the tree is the length shortest path from the root to one of the leaves. It correspons to your intuition of what the heigh of the tree would be.

For example, height of this tree of 15 elements is 4:

Here the tree has 31 elements, and the height is just 5:

And if the double the elements again, the tree height increases just by one: this tree has 63 elements and the height of 6.

Isn't that increadible? Our tree is so large, but the height is still pretty small! In fact, it's just one unit higher than the tree with just half of it's elements.

Funny, right? This tree height grows very slow.

So the height of this tree is indeed logarithm.

No panic! You weren't scared before, right? It's just one pretty tree.

So if the tree has n nodes, the height is approximately log₂n.

For this definition to work, we need the tree to be balanced - so any one part is not much larger than an other.

But you got it! Logarithm is just a height of the tree.

Exhale. Nothing scary. Even nothing much mathematical. Draw this tree to your math teacher. Log is literal log! xD They might just love it :D

log₃n, log₁₀n and other logs

Why log₂n you might ask. Very simple: are nodes had at most two children. If we draw ourselves a tree and allow each node to have 3 children, the height of this tree would be log₃n:

This tree has 1 + 3 + 9 + 27 = 42 nodes.

Every new level has 3 times more nodes than one before that.

Last level, leaves, has more nodes, than all the levels before it.

1. log₃1 = 0
2. log₃3 = 1
3. log₃9 = 2
4. log₃27 = 3

So height of the tree with n nodes will be height >= log₃n.

Asymptotically, height ~ log₃n

And if we allow 10 children, resulting height would be around log₁₀n.

In fact, for us as Computer Scientists doesn't much matter, which log is it.

Because all of logs differ by just a constant:

So as long as you have a tree, you know that it's height is a logarithm.

Most commonly when talking about logarithms, Computer Scientists assume logarithm of two. So you might skip saying log two of an. Say just log an!

You are all set now to use logarithms at full speed! It's not a nightmare - it's just a log!

Quick Summary Here

What is logarithm? Ask Fairy Code Mother!

Practical use of binary search

If you think your knowledge of logarithmic algorithms is useless, think again.