A Common-Sense Guide to Data Structures and Algorithms

Logarithms

Let’s examine why algorithms such as binary search are described as O(log N). What is a log, anyway?

Log is shorthand for logarithm. The first thing to note is that logarithms have nothing to do with algorithms, even though the two words look and sound so similar.

Logarithms are the inverse of exponents. Here’s a quick refresher on what exponents are:

2³ is the equivalent of:

2 * 2 * 2

which just happens to be 8.

Now, log₂ 8 is the converse of the above. It means: how many times do you have to multiply 2 by itself to get a result of 8?

Since you have to multiply 2 by itself 3 times to get 8, log₂ 8 = 3.

Here’s another example:

2⁶ translates to:

2 * 2 * 2 * 2 * 2 * 2 = 64

Since, we had to multiply 2 by itself 6 times to get 64,

log ...