O'Reilly logo

A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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:

23 is the equivalent of:

2 * 2 * 2

which just happens to be 8.

Now, log2 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, log2 8 = 3.

Here’s another example:

26 translates to:

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

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

log ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required