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,
Generalization
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!