1
00:00:00,470 --> 00:00:04,250
‫So now we're going to look at the big oh of merge sort.

2
00:00:04,280 --> 00:00:10,130
‫So I'm going to bring up an array and we're going to start with space complexity.

3
00:00:10,490 --> 00:00:16,940
‫In the first three soaring algorithms that we did, the array was sorted in place.

4
00:00:17,210 --> 00:00:24,080
‫That is to say, we didn't need to create any new data or take up any new space in memory.

5
00:00:24,170 --> 00:00:27,560
‫We just had the original array.

6
00:00:27,890 --> 00:00:32,030
‫But with merge sort, we need to make new arrays.

7
00:00:32,120 --> 00:00:37,010
‫And of course, these are broken in half and these are broken in half.

8
00:00:37,250 --> 00:00:43,010
‫But this takes up as much space in memory as the original array.

9
00:00:43,310 --> 00:00:48,590
‫And that means merge sort four space complexity is o of n.

10
00:00:49,530 --> 00:00:52,530
‫So now let's look at time complexity.

11
00:00:52,860 --> 00:01:00,360
‫The time complexity for merge sort is going to be o of n times log n plus n.

12
00:01:00,840 --> 00:01:08,070
‫So if you'll recall from the big o section, this portion here is what we call a non dominant and we

13
00:01:08,070 --> 00:01:12,480
‫drop non dominance and we're left with o of n times.

14
00:01:12,480 --> 00:01:13,440
‫Log in.

15
00:01:13,860 --> 00:01:16,590
‫So for now, I'm going to bring this back.

16
00:01:16,590 --> 00:01:23,880
‫And this plus n portion is what we're going to do first where we're splitting the arrays in half.

17
00:01:24,120 --> 00:01:27,180
‫So let's count the number of times that we do this.

18
00:01:27,180 --> 00:01:35,340
‫It is one, two, three, four, five, six, seven.

19
00:01:35,670 --> 00:01:39,540
‫So we did this seven times and N is eight.

20
00:01:39,810 --> 00:01:47,760
‫So the number of splits is approximately N and as we discussed previously, this is a non dominant and

21
00:01:47,760 --> 00:01:50,460
‫will be dropped from our equation.

22
00:01:50,970 --> 00:01:57,510
‫So the o of n times log in portion happens when we put everything back together.

23
00:01:57,750 --> 00:02:00,660
‫So N in this case is eight.

24
00:02:00,660 --> 00:02:06,240
‫So we're going to touch all eight of these items, log in times.

25
00:02:06,990 --> 00:02:09,210
‫So now let's walk through this.

26
00:02:09,480 --> 00:02:15,090
‫When we combine these two items, think about the merge function.

27
00:02:15,510 --> 00:02:19,290
‫The wild loops have to touch every value.

28
00:02:19,500 --> 00:02:25,860
‫So it touches both of these and both of these and so on down the line.

29
00:02:26,070 --> 00:02:30,690
‫In order to get to here, we had to touch all in items.

30
00:02:30,900 --> 00:02:37,050
‫And the same is true when we combine these two, we have to touch all four of these and all four of

31
00:02:37,050 --> 00:02:37,770
‫these.

32
00:02:37,800 --> 00:02:41,640
‫Now, once again, we have touched all in items.

33
00:02:41,910 --> 00:02:47,100
‫And then finally, to combine these two, we're having to do the same thing.

34
00:02:47,810 --> 00:02:50,630
‫So let's break this down again like this.

35
00:02:50,630 --> 00:02:58,670
‫So to get to here, we had to touch all in items and that we did it again and then we did it again.

36
00:02:59,180 --> 00:03:08,540
‫We touched all in items three times and if you'll recall from the big O, section four O of log in,

37
00:03:09,050 --> 00:03:11,780
‫log sub two of eight is three.

38
00:03:12,260 --> 00:03:19,730
‫We touched all eight items three times, so the big o of this is o of n times.

39
00:03:19,730 --> 00:03:20,990
‫Log in.

40
00:03:21,200 --> 00:03:25,790
‫We touched in items, log in times.

41
00:03:26,330 --> 00:03:31,460
‫So let's drop these numbers out and take a look at this on the graph.

42
00:03:31,850 --> 00:03:37,880
‫So the big thing we're comparing o of n times log into is o of n squared.

43
00:03:38,030 --> 00:03:42,800
‫So the previous three scoring algorithms were all o of n squared.

44
00:03:43,160 --> 00:03:52,340
‫So in o of n times, log in time complexity is going to be much more efficient and that is merge sort

45
00:03:52,610 --> 00:03:53,630
‫big o.