Logarithms and Time Complexity | Skilled.dev

Logarithms and Time Complexity

Course launching August 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! 🤓

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

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

may use some color coding to combine these?

A logarithm is just inverse of an exponent. If we had the equation log10 1000 = ?, it would read as "if we divide 1000 by 10, how many times would it take for the solution to become 1". So 1000 / 10 = 100 (1 time), 100 / 10 = 10 (2 times), 10 / 10 = 1 (3 times). ^ that's confusing. should I Just say the exponent that will make it equal to 1000?

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

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

show base 2 example 2 2 2 * 2

maybe some visual of dividing in half? [16] -> [8][8] -> [4][4] [4][4] -> [2] .... And blur out the half you're not looking in

Show how many operations logarithms take vs normal with a very straightforward example with visual. Maybe start with 1024 and divide it 10 times visually. "10 operations vs 1024 in O(n)"

Show the log_2 of a bunch of different input sizes vs. O(n)

See below in how logarithms are applied in interviews to understand why this is the case.

Logarithms in Interviews

Binary search, sorting, trees.

Visuals and count numbers. trees is probably the easiest to visualize.

Valid Brackets
Searching and Binary Search

Table of Contents