1
00:00:00,570 --> 00:00:06,330
In this video, let's try to understand all about logarithms with respect to coding interviews, and

2
00:00:06,330 --> 00:00:08,160
the good news is that it is not much.

3
00:00:08,160 --> 00:00:09,960
So let's dive in over here.

4
00:00:09,960 --> 00:00:15,210
Now, whenever we say log n in coding, it's always log in to the base two.

5
00:00:15,210 --> 00:00:19,980
So we typically shorten this and we're just saying log n but it's always to the base two.

6
00:00:19,980 --> 00:00:21,600
Now let's take an example.

7
00:00:21,600 --> 00:00:25,440
Log 16 to the base two is actually equal to four.

8
00:00:25,440 --> 00:00:27,000
Now what does this mean.

9
00:00:27,000 --> 00:00:30,930
It means that two to the power four is equal to 16.

10
00:00:30,930 --> 00:00:35,310
So with the same thing in mind let's try to think about log eight.

11
00:00:35,310 --> 00:00:36,960
So what would be log eight.

12
00:00:36,990 --> 00:00:40,800
Now if you want to find out log eight we can rephrase this.

13
00:00:40,800 --> 00:00:45,210
And we can say two to what power will give me eight.

14
00:00:45,210 --> 00:00:46,350
So that's the same thing over here.

15
00:00:46,350 --> 00:00:46,650
Right.

16
00:00:46,650 --> 00:00:48,150
Two to the power four.

17
00:00:48,180 --> 00:00:51,210
That was the answer over here gave me this 16 over here.

18
00:00:51,210 --> 00:00:54,600
So instead of 16 I have eight because I'm finding log eight.

19
00:00:54,600 --> 00:00:57,600
So two to what power will give me eight.

20
00:00:57,600 --> 00:01:00,660
And we know that two to the power three is equal to eight.

21
00:01:00,660 --> 00:01:03,810
Therefore log eight is equal to three.

22
00:01:03,810 --> 00:01:06,150
So this is what we mean with log n.

23
00:01:06,150 --> 00:01:11,730
Now the interesting thing about log n is that it's a very good time or space complexity.

24
00:01:11,730 --> 00:01:13,230
Because let's take a look.

25
00:01:13,230 --> 00:01:15,960
Let's have a table over here n and log n.

26
00:01:15,960 --> 00:01:17,730
Now let's take two values.

27
00:01:17,730 --> 00:01:26,640
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.

28
00:01:26,640 --> 00:01:31,440
Now if we take log n in both the cases where n is this and this, right?

29
00:01:31,440 --> 00:01:35,880
So when n is 1024, log n is going to be equal to ten.

30
00:01:35,880 --> 00:01:40,830
And when n is equal to this value over here log n is going to be equal to 20.

31
00:01:40,860 --> 00:01:41,220
Again.

32
00:01:41,220 --> 00:01:41,640
Why is that.

33
00:01:41,640 --> 00:01:42,840
So let's try to understand.

34
00:01:42,840 --> 00:01:45,930
So we are taking log two to the power ten.

35
00:01:46,410 --> 00:01:47,430
If you want to find this.

36
00:01:47,430 --> 00:01:48,810
This is nothing but two.

37
00:01:48,840 --> 00:01:50,430
To what power.

38
00:01:51,570 --> 00:01:56,760
Will give me two to the power of ten, and we know that two to the power ten is giving me two to the

39
00:01:56,760 --> 00:01:57,180
power ten.

40
00:01:57,180 --> 00:01:57,450
Right?

41
00:01:57,450 --> 00:02:00,150
So I'm just writing it in this manner to make it easy.

42
00:02:00,150 --> 00:02:01,650
But we could think of it like this.

43
00:02:01,650 --> 00:02:04,800
Also, log 1024 is equal to what?

44
00:02:04,800 --> 00:02:09,180
Which means two to what power will give me 1024, which is ten itself.

45
00:02:09,180 --> 00:02:10,890
So that's why over here we have ten.

46
00:02:10,890 --> 00:02:12,870
And similarly over here we have 20.

47
00:02:12,870 --> 00:02:20,490
So you can see that when n is increasing from 1024 to 1 million something, log n is just increasing

48
00:02:20,490 --> 00:02:21,720
from 10 to 20.

49
00:02:21,720 --> 00:02:26,520
So that's why you can say that log n is a very good time and space complexity.

50
00:02:26,520 --> 00:02:26,970
All right.

51
00:02:26,970 --> 00:02:32,400
Even in the graph which we discussed previously, if you notice you can see that log n is increasing

52
00:02:32,400 --> 00:02:33,990
at a very slow pace.

53
00:02:33,990 --> 00:02:38,490
So if this is constant log n will be going something like this very near to constant.

54
00:02:38,490 --> 00:02:40,080
If n is going somewhere like this.

55
00:02:40,080 --> 00:02:42,780
So that's why the reason for that is over here.

56
00:02:42,780 --> 00:02:43,020
Right.

57
00:02:43,020 --> 00:02:45,540
You can see it's increasing at a very slow pace.

58
00:02:45,540 --> 00:02:48,180
So therefore log n is a very good complexity.

59
00:02:48,180 --> 00:02:48,720
All right.

60
00:02:48,720 --> 00:02:51,240
So we have understood what log n is.

61
00:02:51,240 --> 00:02:53,940
We have understood how to calculate log n right.

62
00:02:53,940 --> 00:02:57,810
For example log eight is nothing but two to what power is equal to eight.

63
00:02:57,810 --> 00:02:59,010
And that is equal to three.

64
00:02:59,010 --> 00:03:00,900
Therefore log eight is equal to three.

65
00:03:00,900 --> 00:03:07,500
Now let's also get some intuition regarding algorithms where let's say the time complexity is log n.

66
00:03:07,500 --> 00:03:14,460
If you have an algorithm that cuts the input in half at every step, then you can say that that relationship

67
00:03:14,460 --> 00:03:15,570
is log n.

68
00:03:15,570 --> 00:03:16,440
Now why is that?

69
00:03:16,440 --> 00:03:17,790
So let's try to understand that.

70
00:03:17,790 --> 00:03:20,940
Let's say we have eight elements and we are searching for some element.

71
00:03:20,940 --> 00:03:24,180
Now we will see this later when we discuss binary search.

72
00:03:24,180 --> 00:03:28,380
But let's say at every step we can eliminate half of the remaining input.

73
00:03:28,380 --> 00:03:31,560
So initially we start with eight things to search through.

74
00:03:31,590 --> 00:03:35,550
Then after one step we only had to search through four more things.

75
00:03:35,550 --> 00:03:40,980
Then after one step we narrowed down to two things, and then we narrowed down to one thing.

76
00:03:40,980 --> 00:03:41,730
So we found it.

77
00:03:41,730 --> 00:03:44,520
So you can see we just have to do three checks over here.

78
00:03:44,820 --> 00:03:47,520
So the size the input size was eight.

79
00:03:47,520 --> 00:03:50,010
And we only had to do three operations.

80
00:03:50,010 --> 00:03:56,970
So you can say that over here the number of operations is of the order of log n or log eight because

81
00:03:56,970 --> 00:03:58,980
three is equal to log eight.

82
00:03:58,980 --> 00:04:04,050
So over here we have a relationship where the time complexity is of the order of log n.

83
00:04:04,050 --> 00:04:06,090
Now this is just to develop an intuition.

84
00:04:06,090 --> 00:04:10,230
We will see this in detail especially in the question where we discuss binary search.

85
00:04:10,230 --> 00:04:17,130
Now another way in which you can think about a time complexity of log n is if you double the input,

86
00:04:17,130 --> 00:04:20,040
you are only going to do one extra operation.

87
00:04:20,040 --> 00:04:22,080
So let's take the same example over here.

88
00:04:22,080 --> 00:04:23,820
We started out with eight elements.

89
00:04:23,820 --> 00:04:26,250
Let's say we start out with 16 elements.

90
00:04:26,250 --> 00:04:29,730
So from 16 we eliminate half and we are left with eight.

91
00:04:29,730 --> 00:04:35,820
From eight we eliminate half and we are left with four from four we eliminate half and we are left with

92
00:04:35,820 --> 00:04:36,240
two.

93
00:04:36,240 --> 00:04:38,250
And then we find the thing right.

94
00:04:38,250 --> 00:04:39,180
So we just have one.

95
00:04:39,180 --> 00:04:41,820
So you can see we just have to do four operations over here.

96
00:04:41,820 --> 00:04:44,790
So we doubled the input from 8 to 16.

97
00:04:44,790 --> 00:04:49,410
But the number of operations only increased by one from 3 to 4.

98
00:04:49,410 --> 00:04:49,920
Over here.

99
00:04:49,920 --> 00:04:52,560
Over here log 16 is equal to four.

100
00:04:52,560 --> 00:04:56,490
That's why this is another way of thinking about log n time complexity.

101
00:04:56,490 --> 00:05:02,310
And you will also come across that in many recursion based questions, the space complexity is going

102
00:05:02,310 --> 00:05:06,840
to be O of log n, because space is going to be consumed in the call stack.

103
00:05:06,840 --> 00:05:08,010
Again, don't worry about this.

104
00:05:08,040 --> 00:05:11,640
We will see this in detail in the future part of this course.