‫In this video, we're going to look at the big o of vectors.
‫And most of what I'm going to talk about in this video will also apply to arrays.
‫And when we have a vector or an array, it usually looks something like this.
‫I'm going to graphically represent this like this.
‫It'll just be a little easier to look at.
‫And then we can also include the indexes.
‫So I'm going to call this vector my vector, and then we'll look at a variety of things that we do with
‫vectors.
‫So we'll start out by saying dot pushback with the number 17, and that adds that to the end.
‫And from a big O perspective with vectors or arrays in is going to be the number of items in that data
‫structure.
‫And to add something to the end, we don't have to touch any of these other items.
‫Likewise, when we remove this item and we'll do that by saying dot pop back and that'll remove that,
‫we don't have to touch anything else in the vector.
‫And because of that, adding or removing an item from a vector is going to be o of one.
‫So now let's look at removing an item from the other end of the vector.
‫We'll say my vector dot erase and we'll pass this, my vector begin, which is that first item.
‫But when we remove that, the problem we have is this is no longer the correct index.
‫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
‫in the vector.
‫Likewise, if we're going to add that item back in, we'll say dot insert at that first index.
‫My vector begin will put that number 11 back.
‫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
‫the line.
‫To be able to put that 11 right there.
‫So it doesn't matter if you're adding or removing from the beginning because you have to touch every
‫item in the vector.
‫This will be o of.
‫So the most important thing to remember is that if you are adding or removing from the end, it's a
‫of one.
‫But on the other end it doesn't matter if you are removing because of all of the re indexing or adding
‫once again because of all of the re indexing, this is going to be o of n.
‫So now let's look at adding an item.
‫Somewhere in the middle will say my vector.
‫Dot insert.
‫And we're going to say at the beginning, plus one, which is going to be that index there, and we're
‫going to insert the number 99.
‫Like that when we insert that.
‫Now, this index is going to be incorrect.
‫We need to change this to two and do the same thing all the way down.
‫And because we're going to have to touch all of those items, that's going to make this o of n.
‫And you might be thinking, if we're inserting this somewhere in the middle, shouldn't this be one
‫half in?
‫So there are a couple of problems with that logic.
‫First, big O is worst case, not average case.
‫But even if this was O of one half in one half is a constant and we drop constants.
‫So either way this is o of NW.
‫Likewise, when we go to remove this item, we're going to have to re index everything after it and
‫that also will be o of n.
‫So now let's look at finding an item by value.
‫Let's say we're looking for the number seven in this vector.
‫In order to do that, we start with the first item and check to see if it has a value of seven.
‫And then we iterate through the vector until we finally find the value of seven.
‫So looking up by value is o of n.
‫But if we're looking up by index, we can go directly to that place in memory in one step, which means
‫it is o of one.
‫So looking up by value as o of n and looking up by index is o of one.
‫And that is our overview of the big o of vectors.