In this video, let's try to understand all about logarithms with respect to coding interviews, and
the good news is that it is not much.
So let's dive in over here.
Now, whenever we say log n in coding, it's always log in to the base two.
So we typically shorten this and we're just saying log n but it's always to the base two.
Now let's take an example.
Log 16 to the base two is actually equal to four.
Now what does this mean.
It means that two to the power four is equal to 16.
So with the same thing in mind let's try to think about log eight.
So what would be log eight.
Now if you want to find out log eight we can rephrase this.
And we can say two to what power will give me eight.
So that's the same thing over here.
Right.
Two to the power four.
That was the answer over here gave me this 16 over here.
So instead of 16 I have eight because I'm finding log eight.
So two to what power will give me eight.
And we know that two to the power three is equal to eight.
Therefore log eight is equal to three.
So this is what we mean with log n.
Now the interesting thing about log n is that it's a very good time or space complexity.
Because let's take a look.
Let's have a table over here n and log n.
Now let's take two values.
Let n be two to the power ten which is 1024, and let it be two to the power 20, which is 1,048,576.
Now if we take log n in both the cases where n is this and this, right?
So when n is 1024, log n is going to be equal to ten.
And when n is equal to this value over here log n is going to be equal to 20.
Again.
Why is that.
So let's try to understand.
So we are taking log two to the power ten.
If you want to find this.
This is nothing but two.
To what power.
Will give me two to the power of ten, and we know that two to the power ten is giving me two to the
power ten.
Right?
So I'm just writing it in this manner to make it easy.
But we could think of it like this.
Also, log 1024 is equal to what?
Which means two to what power will give me 1024, which is ten itself.
So that's why over here we have ten.
And similarly over here we have 20.
So you can see that when n is increasing from 1024 to 1 million something, log n is just increasing
from 10 to 20.
So that's why you can say that log n is a very good time and space complexity.
All right.
Even in the graph which we discussed previously, if you notice you can see that log n is increasing
at a very slow pace.
So if this is constant log n will be going something like this very near to constant.
If n is going somewhere like this.
So that's why the reason for that is over here.
Right.
You can see it's increasing at a very slow pace.
So therefore log n is a very good complexity.
All right.
So we have understood what log n is.
We have understood how to calculate log n right.
For example log eight is nothing but two to what power is equal to eight.
And that is equal to three.
Therefore log eight is equal to three.
Now let's also get some intuition regarding algorithms where let's say the time complexity is log n.
If you have an algorithm that cuts the input in half at every step, then you can say that that relationship
is log n.
Now why is that?
So let's try to understand that.
Let's say we have eight elements and we are searching for some element.
Now we will see this later when we discuss binary search.
But let's say at every step we can eliminate half of the remaining input.
So initially we start with eight things to search through.
Then after one step we only had to search through four more things.
Then after one step we narrowed down to two things, and then we narrowed down to one thing.
So we found it.
So you can see we just have to do three checks over here.
So the size the input size was eight.
And we only had to do three operations.
So you can say that over here the number of operations is of the order of log n or log eight because
three is equal to log eight.
So over here we have a relationship where the time complexity is of the order of log n.
Now this is just to develop an intuition.
We will see this in detail especially in the question where we discuss binary search.
Now another way in which you can think about a time complexity of log n is if you double the input,
you are only going to do one extra operation.
So let's take the same example over here.
We started out with eight elements.
Let's say we start out with 16 elements.
So from 16 we eliminate half and we are left with eight.
From eight we eliminate half and we are left with four from four we eliminate half and we are left with
two.
And then we find the thing right.
So we just have one.
So you can see we just have to do four operations over here.
So we doubled the input from 8 to 16.
But the number of operations only increased by one from 3 to 4.
Over here.
Over here log 16 is equal to four.
That's why this is another way of thinking about log n time complexity.
And you will also come across that in many recursion based questions, the space complexity is going
to be O of log n, because space is going to be consumed in the call stack.
Again, don't worry about this.
We will see this in detail in the future part of this course.