So what is O(log n) Time Complexity Anyway?

What is Time Complexity?

Time complexity is a fairly simple concept to grasp, but becomes more and more complex with the algorithms that it exists to categorize. At its most basic, time complexity describes the time it takes for an algorithm to execute (O) based on its input (n).

What is a logarithm?

So now that we know that n is the input of the algorithm, what is a logarithm in the first place? Well the definition of a logarithm is:

A quantity representing the power to which a fixed number (the base) must be raised to produce a given number.

So what does that mean? Well let’s take this example:

2^x = n
log_2 n
x = log_2 n
(2^x = n) = (x = log_2 n)

What about in Code?

So armed with the knowledge of what a logarithm actually is, how do we make use of that when writing code? Well one of the most common O(log n) algorithms is binary search. Basically, this is a method of finding a given value in a sorted array by dividing said array in half increasingly in order to find the right value. This is what a binary search algorithm might look like in python:

def binary_search(list1, low, high, n):   if low <= high:   mid = (low + high) // 2   if list1[mid] == n:      return mid   elif list1[mid] > n:      return binary_search(list1, low, mid — 1, n)   else:      return binary_search(list1, mid + 1, high, n)   else:      return -1
[1, 3, 5, 8, 12, 13, 15, 16, 18, 20, 22, 30, 40, 50, 55, 67]
[1, 3, 5, 8, 12, 13, 15, 16, 18, 20, 22, 30, 40, 50, 55, 67]
[1, 3, 5, 8, 12, 13, 15, 16, 18, 20, 22, 30, 40, 50, 55, 67]
[1, 3, 5, 8, 12, 13, 15, 16, 18, 20, 22, 30, 40, 50, 55, 67]
16 * (1/2)^4 = 1
n * (1/2)^4 = 1
n * (1/2)^x = 1
n * 1/2^x = 1
n/2^x = 1
2^x * n/2^x = 2^x
n = 2^x

A quantity representing the power to which a fixed number (the base) must be raised to produce a given number.

So using our previous logic, we can decipher that

(n = 2^x or 2^x = n) = (x = log_2 n)

Is There an Easier Way to Tell?

That’s all fine and dandy, but the problem is that the average developer doesn’t want to meticulously run through that operation all the time. Fortunately, O(log n) algorithms have a common behavior that’s easier to pick up on.

Conclusion

Time complexity is confusing in its own right, O(log n) time adds another layer. However, understanding this is very important because it can help you create faster code by utilizing O(log n)’s ability to shrink the input every iteration. I hope that this post helps someone understand O(log n) time a lot faster than it took me.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Aidan Tilgner

Aidan Tilgner

50 Followers

Software Developer working my way through the world and sharing what I learn with all of you. Personal Site — www.aidantilgner.dev