What does the time complexity O(log n) actually mean? by@maazrk
249,818 reads

What does the time complexity O(log n) actually mean?

May 28th 2017
by @maazrk 249,818 reads
Read on Terminal Reader

Too Long; Didn't Read

Company Mentioned

Mention Thumbnail
featured image - What does the time complexity O(log n) actually mean?
react to story with heart

Knowing the complexity of algorithms beforehand is one thing, and other thing is knowing the reason behind it being like that.

Whether you’re a CS graduate or someone who wants to deal with optimization problems effectively, this is something that you must understand if you want to use your knowledge for solving actual problems.

Complexities like O(1) and O(n) are simple and straightforward. O(1) means an operation which is done to reach an element directly (like a dictionary or hash table), O(n) means first we would have to search it by checking n elements, but what could O(log n) possibly mean?

One place where you might have heard about O(log n) time complexity the first time is Binary search algorithm. So there must be some type of behavior that algorithm is showing to be given a complexity of log n. Let us see how it works.

Since binary search has a best case efficiency of O(1) and worst case (average case) efficiency of O(log n), we will look at an example of the worst case. Consider a sorted array of 16 elements.

For the worst case, let us say we want to search for the the number 13.


A sorted array of 16 elements


Selecting the middle element as pivot (length / 2)


Since 13 is less than pivot, we remove the other half of the array


Repeating the process for finding the middle element for every sub-array



You can see that after every comparison with the middle term, our searching range gets divided into half of the current range.

So, for reaching one element from a set of 16 elements, we had to divide the array 4 times,

We can say that,


Simplified Formula

Similarly, for n elements,




Separating the power for the numerator and denominator


Multiplying both sides by 2^k


Final result

Now, let us look at the definition of logarithm, it says that

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

Which makes our equation into


Logarithmic form

So the log n actually means something doesn’t it? A type of behavior nothing else can represent.

Well, i hope the idea of it is clear in your mind. When working in the field of computer science, it is always helpful to know such stuff (and is quite interesting too). Who knows, maybe you’re the one in your team who is able to find an optimized solution for a problem, just because you know what you’re dealing with. Good luck!


. . . comments & more!
Hackernoon hq - po box 2206, edwards, colorado 81632, usa