In computer science, by definition, "Time Complexity" means the amount of time taken to run an algorithm. An algorithm runs on an input data and the time taken by algorithm to process the input data varies with the amount of input data. O(N) is the simplest one to understand where we know there is a linear relation of a time to the size of an input data. But things start getting confusing as soon as we introduce "Log" to the party, mathematical background of Logarithms makes people even more afraid of it.
However, if we keep our intention to understand Log(N) only from time complexity perspective, it is not difficult at all. Let me try and explain;
Pre-requisites:
Input Data Size = N
Problem to solve on this data.
Algorithm to solve this problem.
Let's consider how the graph of the powers of 2 grows and then come back to understand how it relates to Log(N).
2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 32 and so on.
The generalised equation becomes;
2^index = N
It is very clear from the above equation that with just the increase of 1 in the index, the result N, doubles. It is an exponential growth.
If we reverse the equation and start reducing the result to half, the index decreases only by 1.
32 = 2^5
16 = 2^4
08 = 2^3
04 = 2^2
02 = 2^1
01 = 2^0
Now, let's try and relate it back to our problem and the algorithm to solve it. If our algorithm is efficient enough to divide the input data in half every-time it processes the data in order to solve the problem, then our algorithm is said to have a time complexity of Log(N)
With all the explanation above, following equations are the different representations of the same thing.
Log(8) = 3 -> 2^3 = 8 -> Log(N) = index
To put it in a sentence, "To process the input data of size N, it will take the Log(N) i.e. 'index' amount of time."
Importance of "2" in Log(N)
Why we took an example of 2?
Because in order to solve the problem, we are dividing the input data in to the half (1/2) every time we process it, eliminating the need to process the half of the data. And that's why, here it's the Log to the base of 2. In computer science whenever we talk about Log, it is always to the base of 2.
Top comments (0)