1
00:00:00,410 --> 00:00:03,500
‫Now let's look at o of log in.

2
00:00:03,680 --> 00:00:08,210
‫And to explain this, I'm going to bring up a sorted array.

3
00:00:08,210 --> 00:00:12,380
‫And to do what we're about to do here, the data does have to be sorted.

4
00:00:12,740 --> 00:00:16,460
‫So let's say we want to find a particular value in this array.

5
00:00:16,460 --> 00:00:19,400
‫We'll say we're going to look for the number one.

6
00:00:19,940 --> 00:00:25,460
‫What is the quickest way to narrow this down to get to that one?

7
00:00:26,090 --> 00:00:32,420
‫Well, the quickest way would be to cut the array in half and see if the one is in the first half or

8
00:00:32,420 --> 00:00:33,470
‫the second half.

9
00:00:33,950 --> 00:00:36,080
‫So it is not in the second half.

10
00:00:36,080 --> 00:00:41,090
‫So we don't have to look at any of those numbers so we can remove those.

11
00:00:41,660 --> 00:00:45,920
‫And that may not seem like a big deal when you have an array with only eight items in it.

12
00:00:45,920 --> 00:00:52,040
‫But if you had an array with a million items in it, that's a half a million items that you don't have

13
00:00:52,040 --> 00:00:52,610
‫to look at.

14
00:00:52,610 --> 00:00:54,650
‫So that is a pretty big deal.

15
00:00:54,860 --> 00:01:00,110
‫So then we can take the array and do this again and we know it's not on the second half.

16
00:01:00,110 --> 00:01:06,950
‫So we can remove those and then we'll do it again and then we'll find the number that we're looking

17
00:01:06,950 --> 00:01:07,460
‫for.

18
00:01:07,850 --> 00:01:14,780
‫So let's bring back all of the other items in the array and look at how many steps this took to find

19
00:01:14,780 --> 00:01:15,980
‫the number one.

20
00:01:16,130 --> 00:01:20,600
‫It was one, two, three steps.

21
00:01:21,140 --> 00:01:24,560
‫And remember, we had eight items in this array.

22
00:01:24,560 --> 00:01:29,450
‫And it just so happens that two to the third power is eight.

23
00:01:29,870 --> 00:01:36,380
‫So now I'm going to take this equation and turn it into a logarithm and we're not going to get really

24
00:01:36,380 --> 00:01:37,550
‫deep into this math.

25
00:01:37,550 --> 00:01:38,870
‫This will be pretty simple.

26
00:01:39,110 --> 00:01:46,310
‫But when we convert this to a logarithm, it looks like this log sub two of eight equals three.

27
00:01:46,790 --> 00:01:50,540
‫And I'm going to put this back and let's look at this again.

28
00:01:50,540 --> 00:01:53,930
‫Log sub two of eight equals three.

29
00:01:54,630 --> 00:02:02,040
‫So what this is basically saying is to to the what power equals eight.

30
00:02:02,860 --> 00:02:05,500
‫To to the what power equals eight?

31
00:02:05,890 --> 00:02:09,400
‫Well, two to the third power equals eight.

32
00:02:09,880 --> 00:02:17,680
‫To put it another way, if you took the number eight and you repeatedly divided it by two, how many

33
00:02:17,680 --> 00:02:20,200
‫times would it take to get down to one item?

34
00:02:20,590 --> 00:02:22,870
‫And that is three times.

35
00:02:23,480 --> 00:02:28,640
‫But the real power of this is when we're dealing with very large numbers.

36
00:02:28,640 --> 00:02:34,010
‫Let's say we take logs of two of this number and this is over a billion.

37
00:02:34,460 --> 00:02:42,740
‫How many times would you need to cut this number in half to get down to one item and it is 31 times.

38
00:02:43,280 --> 00:02:51,710
‫So you could have an array with over a billion items in it and find any number in that array in 31 steps.

39
00:02:52,190 --> 00:02:55,790
‫And that is the power of o of log in.

40
00:02:56,150 --> 00:02:59,720
‫So now let's take this and look at it on a graph.

41
00:03:00,910 --> 00:03:05,350
‫So you can see that this is very flat, very efficient.

42
00:03:05,380 --> 00:03:11,200
‫It's not as efficient as oh of one, of course, but it is the next best thing.

43
00:03:11,680 --> 00:03:18,640
‫And so everything we're going to look at this course is going to be one of these four, except for I'm

44
00:03:18,640 --> 00:03:27,460
‫going to show one other one here, and this one is o of n times log in that is used with some sorting

45
00:03:27,460 --> 00:03:28,300
‫algorithms.

46
00:03:28,750 --> 00:03:32,980
‫So we're going to see this with quicksort and merge sort.

47
00:03:33,100 --> 00:03:38,080
‫But other than that, everything else will be one of these for.

48
00:03:38,780 --> 00:03:39,890
‫So that.

49
00:03:40,680 --> 00:03:41,970
‫Izzo of log in.