1
00:00:00,420 --> 00:00:03,300
Now let's explore space complexity.

2
00:00:03,330 --> 00:00:10,110
We have already seen that time complexity is how the runtime increases as the input size increases.

3
00:00:10,140 --> 00:00:17,340
Now, space complexity in a similar manner deals with the extra space consumed by the algorithm as the

4
00:00:17,340 --> 00:00:18,870
input size increases.

5
00:00:18,870 --> 00:00:26,280
So again, as the case of time complexity, space complexity is also expressed using Big-O notation

6
00:00:26,280 --> 00:00:26,790
itself.

7
00:00:26,790 --> 00:00:33,780
So if you say that the space complexity of an algorithm is O of one, it means that the space required

8
00:00:33,780 --> 00:00:38,310
by the algorithm to run does not scale as the input size scales.

9
00:00:38,310 --> 00:00:44,760
Similarly, if you have an O of n space complexity, it means that the space requirement by the algorithm

10
00:00:44,760 --> 00:00:47,790
scales linearly as the input size grows.

11
00:00:47,790 --> 00:00:53,940
Now this over here space complexity, let me just write it over here means how much auxiliary memory

12
00:00:53,940 --> 00:00:56,100
is needed to run the algorithm.

13
00:00:56,100 --> 00:00:58,200
So over here we have an interesting point.

14
00:00:58,200 --> 00:01:04,530
We only deal with the auxiliary memory or extra memory, which is the space required or additional space

15
00:01:04,530 --> 00:01:06,840
required only by the algorithm.

16
00:01:06,840 --> 00:01:09,870
We don't consider the size of the input.

17
00:01:09,870 --> 00:01:15,900
It's understood that as the input size increases to store the input, we would require more space.

18
00:01:15,900 --> 00:01:17,880
But we are not going to consider that.

19
00:01:17,880 --> 00:01:23,910
When we evaluate the efficiency of the algorithm, we only deal with the extra space required by the

20
00:01:23,910 --> 00:01:25,500
algorithm to execute.

21
00:01:25,500 --> 00:01:25,920
All right.

22
00:01:25,920 --> 00:01:28,920
So that is what space complexity is about.

23
00:01:28,920 --> 00:01:30,990
Now a few interesting pointers.

24
00:01:30,990 --> 00:01:37,710
In some coding interview questions, you can see that we can improve the time complexity by using up

25
00:01:37,710 --> 00:01:38,640
more space.

26
00:01:38,640 --> 00:01:43,830
So in those cases it's a trade off between time complexity and space complexity.

27
00:01:43,830 --> 00:01:49,590
In some solutions, maybe you can see that you can improve the time complexity by storing some values

28
00:01:49,590 --> 00:01:52,590
in a new array, or a string, or a hash map, etc..

29
00:01:52,590 --> 00:01:52,890
Right?

30
00:01:52,890 --> 00:01:55,980
So in those cases there would be some space used up.

31
00:01:55,980 --> 00:02:03,210
Now also remember primitives such as numbers, boolean, null, undefined, etc. all take up constant

32
00:02:03,210 --> 00:02:03,690
space.

33
00:02:03,690 --> 00:02:06,840
So we have got a good idea about space complexity as well.

34
00:02:06,840 --> 00:02:11,790
Now let's take a look at a few techniques to simplify Big-O expressions.

35
00:02:11,790 --> 00:02:16,860
So these are again things that we have discussed while we discussed the asymptotic analysis.

36
00:02:16,860 --> 00:02:20,520
But over here let's just discuss it as pointers to techniques.

37
00:02:20,520 --> 00:02:23,040
So the first technique is drop the constant.

38
00:02:23,040 --> 00:02:30,750
So for example if you have the time complexity or the space complexity as O of 25 into n square, drop

39
00:02:30,750 --> 00:02:35,010
the constant and you can say that it simplifies to o of n square.

40
00:02:35,010 --> 00:02:39,540
The second pointer is drop in significant terms as n increases.

41
00:02:39,540 --> 00:02:39,810
Right.

42
00:02:39,810 --> 00:02:42,750
So we have seen this in the case of asymptotic analysis.

43
00:02:42,750 --> 00:02:49,230
So if you see that the expression is O of n cube plus 100 n, then you can drop this because this is

44
00:02:49,230 --> 00:02:49,950
a constant.

45
00:02:49,950 --> 00:02:54,990
And then you can drop n because compared to n cube n is going to be insignificant.

46
00:02:54,990 --> 00:02:56,610
So you can drop that.

47
00:02:56,610 --> 00:02:59,100
And this simplifies to o of n cube.

48
00:02:59,100 --> 00:03:04,830
Now the third point is if there are different input parameters this is something that you should remember.

49
00:03:04,830 --> 00:03:06,120
You cannot drop them.

50
00:03:06,120 --> 00:03:12,480
For example, if you have O of n cube plus M, you cannot drop this M because you have n cube over here.

51
00:03:12,480 --> 00:03:13,920
So that's an important thing.

52
00:03:13,920 --> 00:03:14,280
All right.

53
00:03:14,280 --> 00:03:15,210
So why is that.

54
00:03:15,210 --> 00:03:20,880
So for example there can be a scenario where n is just one but m is 10,000.

55
00:03:20,880 --> 00:03:24,090
So you can see that in that case m is much bigger than n cube.

56
00:03:24,090 --> 00:03:26,070
So that's why this is a possibility right.

57
00:03:26,070 --> 00:03:27,690
So this is a valid possibility.

58
00:03:27,690 --> 00:03:33,630
So if the input parameters are different then you cannot drop them just because one is of greater power

59
00:03:33,630 --> 00:03:34,320
etc..

60
00:03:34,320 --> 00:03:36,870
Like if this was n then we would have dropped it.

61
00:03:36,870 --> 00:03:39,960
But because both of them are different you cannot drop them.

62
00:03:39,960 --> 00:03:40,380
All right.

63
00:03:40,380 --> 00:03:45,420
So these are three interesting techniques that you can keep in mind to simplify Big-O expressions.

64
00:03:45,420 --> 00:03:49,410
Now let's come to the final part and let's discuss logarithms.