1
00:00:00,460 --> 00:00:04,600
‫In this video, we're going to look at the big o of vectors.

2
00:00:04,960 --> 00:00:10,330
‫And most of what I'm going to talk about in this video will also apply to arrays.

3
00:00:10,750 --> 00:00:15,790
‫And when we have a vector or an array, it usually looks something like this.

4
00:00:15,790 --> 00:00:20,290
‫I'm going to graphically represent this like this.

5
00:00:20,680 --> 00:00:22,780
‫It'll just be a little easier to look at.

6
00:00:22,780 --> 00:00:26,050
‫And then we can also include the indexes.

7
00:00:26,050 --> 00:00:32,560
‫So I'm going to call this vector my vector, and then we'll look at a variety of things that we do with

8
00:00:32,560 --> 00:00:33,070
‫vectors.

9
00:00:33,070 --> 00:00:40,540
‫So we'll start out by saying dot pushback with the number 17, and that adds that to the end.

10
00:00:40,870 --> 00:00:49,060
‫And from a big O perspective with vectors or arrays in is going to be the number of items in that data

11
00:00:49,060 --> 00:00:49,810
‫structure.

12
00:00:49,840 --> 00:00:55,420
‫And to add something to the end, we don't have to touch any of these other items.

13
00:00:55,420 --> 00:01:03,250
‫Likewise, when we remove this item and we'll do that by saying dot pop back and that'll remove that,

14
00:01:03,670 --> 00:01:07,600
‫we don't have to touch anything else in the vector.

15
00:01:07,780 --> 00:01:14,770
‫And because of that, adding or removing an item from a vector is going to be o of one.

16
00:01:15,010 --> 00:01:19,150
‫So now let's look at removing an item from the other end of the vector.

17
00:01:19,150 --> 00:01:29,710
‫We'll say my vector dot erase and we'll pass this, my vector begin, which is that first item.

18
00:01:29,710 --> 00:01:36,400
‫But when we remove that, the problem we have is this is no longer the correct index.

19
00:01:36,640 --> 00:01:45,790
‫So we have to change that index of 1 to 0 and we have to do that all the way down and touch every item

20
00:01:45,790 --> 00:01:46,720
‫in the vector.

21
00:01:46,990 --> 00:01:55,150
‫Likewise, if we're going to add that item back in, we'll say dot insert at that first index.

22
00:01:55,150 --> 00:01:59,440
‫My vector begin will put that number 11 back.

23
00:01:59,440 --> 00:02:08,080
‫In order to do that, we have to change this index to a three and then this one to a two and so on down

24
00:02:08,080 --> 00:02:08,950
‫the line.

25
00:02:09,690 --> 00:02:12,360
‫To be able to put that 11 right there.

26
00:02:12,690 --> 00:02:19,560
‫So it doesn't matter if you're adding or removing from the beginning because you have to touch every

27
00:02:19,560 --> 00:02:20,790
‫item in the vector.

28
00:02:21,210 --> 00:02:22,740
‫This will be o of.

29
00:02:23,820 --> 00:02:32,480
‫So the most important thing to remember is that if you are adding or removing from the end, it's a

30
00:02:32,480 --> 00:02:33,330
‫of one.

31
00:02:33,690 --> 00:02:41,730
‫But on the other end it doesn't matter if you are removing because of all of the re indexing or adding

32
00:02:41,730 --> 00:02:47,310
‫once again because of all of the re indexing, this is going to be o of n.

33
00:02:47,820 --> 00:02:49,590
‫So now let's look at adding an item.

34
00:02:49,590 --> 00:02:53,190
‫Somewhere in the middle will say my vector.

35
00:02:54,170 --> 00:02:55,700
‫Dot insert.

36
00:02:55,970 --> 00:03:02,690
‫And we're going to say at the beginning, plus one, which is going to be that index there, and we're

37
00:03:02,690 --> 00:03:05,690
‫going to insert the number 99.

38
00:03:06,290 --> 00:03:09,530
‫Like that when we insert that.

39
00:03:09,860 --> 00:03:12,590
‫Now, this index is going to be incorrect.

40
00:03:12,590 --> 00:03:17,600
‫We need to change this to two and do the same thing all the way down.

41
00:03:17,930 --> 00:03:23,420
‫And because we're going to have to touch all of those items, that's going to make this o of n.

42
00:03:23,930 --> 00:03:28,640
‫And you might be thinking, if we're inserting this somewhere in the middle, shouldn't this be one

43
00:03:28,640 --> 00:03:29,660
‫half in?

44
00:03:30,140 --> 00:03:32,840
‫So there are a couple of problems with that logic.

45
00:03:32,840 --> 00:03:37,940
‫First, big O is worst case, not average case.

46
00:03:38,510 --> 00:03:46,520
‫But even if this was O of one half in one half is a constant and we drop constants.

47
00:03:46,520 --> 00:03:49,520
‫So either way this is o of NW.

48
00:03:49,970 --> 00:03:56,390
‫Likewise, when we go to remove this item, we're going to have to re index everything after it and

49
00:03:56,390 --> 00:03:59,300
‫that also will be o of n.

50
00:03:59,810 --> 00:04:03,290
‫So now let's look at finding an item by value.

51
00:04:03,290 --> 00:04:07,340
‫Let's say we're looking for the number seven in this vector.

52
00:04:07,820 --> 00:04:13,490
‫In order to do that, we start with the first item and check to see if it has a value of seven.

53
00:04:13,880 --> 00:04:20,660
‫And then we iterate through the vector until we finally find the value of seven.

54
00:04:20,660 --> 00:04:24,800
‫So looking up by value is o of n.

55
00:04:25,870 --> 00:04:33,730
‫But if we're looking up by index, we can go directly to that place in memory in one step, which means

56
00:04:33,730 --> 00:04:35,260
‫it is o of one.

57
00:04:35,560 --> 00:04:42,550
‫So looking up by value as o of n and looking up by index is o of one.

58
00:04:43,390 --> 00:04:48,580
‫And that is our overview of the big o of vectors.