Logarithms and Time Complexity | Skilled.dev
Learn

Logarithms and Time Complexity

Course launching November 17, 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓
Loading...

Logarithms like log(n) can be intimidating at first because they feel so closely connected to math, similar to Big O. However, you only need to understand a few basic points about them to apply them to your coding interviews. This article will make logarithms dead simple and show you how use the concept in interviews.

Simplifying the Math

  • Exponents => multiplication
  • Logarithms => division

If we asked for an exponent 23 = ?, most people can quickly realize that the answer is 8. It reads as "if we multiplied 2 times itself 3 times, it would equal 8" or 23 = 2 x 2 x 2 = 8

A logarithm is just inverse of an exponent. If we had the equation log2(8) = ?, it would read as "if we divide 8 by 2, how many times would it take for the solution to become 1". This would be:

log2(8) = 3

8 / 2 / 2 / 2 = 1
    -   -   -
    1   2   3

I stated logarithms and exponents are inverse operations, just like division and multiplication, but that may not have been immediately obvious. If you have log2(8) = ?, it's equivalent to saying 2? = 8.

All logarithms need a base, and in the above example we used 2. When we've used the Big O O(log n), we're typically assuming a base of 2 for O(log2 n). The reason we assume 2 is because the most common operation is to divide by 2 repeatedly each time we perform a pass over the input.

If we change the base though, the logic is still the same. For example, log10(100) = 2, log10(1000) = 3, log10(10000) = 4, and so on.

So if we had an input size of 16, if we had a O(log n) algorithm, it would touch only ~4 items instead of all 16.

This is an example of a binary search. Each time we make a move, we cut out half the items because the list is sorted and we know 16 is larger than the current middle item. If we were to linearly search this, we would start at the beginning and iterate through all n items.

input size
n
O(n)O(log n)
221
442
883
16164
.........
1024102410
2048204811
4096409612
.........
1048576104857620

So you can see that as the number of items in our input increases, the linear O(n) complexity grows at the same rate, but O(log n) increases very slowly even for large input. For example, if you have an input size of 1,048,576, it would only take 20 operations for a O(log n) algorithm. This is because you divide the input by 2 each time, and you only need to do this 20 times for 1,048,576 to reach 1.

In interviews, you most often see logarithmic time in binary search or iterating through a binary search tree. However, as long as you can recognize that your input is being divided on every iteration, this is an indication of O(log n) time.

Prev
Valid Brackets
Next
Searching and Binary Search
Loading...

Table of Contents