A Common-Sense Guide to Data Structures and Algorithms in JavaScript, Volume 1

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 word logarithm has nothing to do with algorithm, 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.

This just happens to be 8.

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

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

Here’s another example:

2⁶ translates to

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

Because we had to multiply 2 by itself six times to get 64, we have, ...