Matrix vs List Comparison

[00:00:00]
>> Bianca Gandolfo: How do we add a node to the adjacency list?
>> Speaker 2: Just insert at the end?
>> Bianca Gandolfo: Yeah so we would just insert. If we were going to add six, we would just put a six right here.
>> Bianca Gandolfo: Let's do this. I have a solution here let's, look at it like this.

[00:00:35]
>> Bianca Gandolfo: Okay so if we wanted to add a six we do something like this, right? What about for this one?
>> Speaker 2: Times zero, zero, zero, zero.
>> Bianca Gandolfo: Yeah, so we would need to add something like this, and then we'd also have to do this, yeah.
>> Speaker 3: But that is still constant.

[00:01:07]
Correct?
>> Speaker 4: You have to find out how long it is.
>> Speaker 2: That is based on numbers. The number of operations.
>> Bianca Gandolfo: Well, but how many pushes.
>> Speaker 3: The number of operations depends on
>> Speaker 2: The number of nodes.
>> Speaker 3: And how many [INAUDIBLE]
>> Bianca Gandolfo: Yeah, so the time complexity of adding this is based on how many nodes so that's like, so if we have, so it's linear time.

[00:01:32]
And when we think about graph time complexity, there's another interesting thing to consider Usually when we were talking about trees in linear data structures, we just were only thinking about n as in nodes, but with a graph we also need to consider the edges because often there's gonna be more work that needs to be done if there's extra edges.

[00:01:54]
So it could be v times e, right? So the vertices times the edges for something. So just consider that when you're thinking about graphs. And also in general when you're thinking about time complexity, think what is n? What is n, right? It has to be, is n for our tree, n is the number of nodes, right, in the tree.

[00:02:21]
In an array, often n is the length of the array, right? But it's not always true, so just think about that when you're reasoning about it.
>> Bianca Gandolfo: Cool. So we're gonna have to loop through this, add zeroes for each one and we're gonna have to add another one at the end.

[00:02:40]
So the adding of the zero is gonna be constant time, but the looping through to get there is the linear time operation. And because we're only thinking about orders of magnitude we just don't care about the cost of time anymore and then this is just linear.