[NOISE] >> In this concept challenge, we're gonna be looking at how much space is required to represent a graph. So remember, the concept challenges. You're gonna first gonna think about this on your own. You're gonna discuss this with other learners, if you have them around. You're gonna watch our UC San Diego learners discuss it, then you're gonna answer the question again. And lastly, you'll get to confirm your understanding with us with our discussion. So first, a warm up question. What I want you to do is think about how much space is required to represent a graph as a matrix. So this is Big-O, Tightest Bound. So go ahead and think about this on your own, answer the in video quiz. See you back in a moment. So I'm hoping you saw when you worked through this problem alone was that if you're going to represent this as a matrix, what you end up is with the number of verses is the number of columns and a number verses is the number of rows. So if you number the verses as columns times the number of verses as rows, you're going to end up with O of V squared, which is the correct answer for this question. And as a quick aside I want to ask you, what would change if I made this a undirected graph? Well, not much changes actually. So what you'll notice is I've already changed our graph structure here to be undirected and all you'll notice is that, it's essentially a symmetric matrix. You're gonna see that half the information here is essentially redundant, but still Big-O of V squared. So the next question is when we start working with adjacency lists, how much storage is required for that representation? Go ahead and work on this on your own, listen to the UCSD learners discuss it and then I'll see you back in a few moments. >> Hi, my name is Huang. >> My name is Paul. >> My name is Umay >> So let's get started. >> So, I think adjacency list has to be different from adjacency matrix. So I don't think that D or E are right, because they are still squared for the magnitude of both the vertices and the number of edges. >> Yeah, I agree with you. I think the answer should be one of A, B or C. Because in order to store the graph, you have to store edges and vertices, but I'm not sure if you have to store both. >> Well, each vertices should know what edges are connected to it. So, what if there's no edges? >> Welcome back. I hope that UCSD learners discussing it was helpful. What we're gonna do to solve this is just look at the representation. So if we had this representation for this graph, what you're gonna recognize is that the number of rows here are the number of vertices. So this is essentially O of the number of vertices. And if you start trying to think about how many edges are represented per vertex, this gets fairly complex. But if you just realize the sum of all the edges represented here is just the sum of edges, it's a lot easier. So we have here is the number of vertices is the rows, the number of edges, essentially has what's contained within all those O's rows and what does this end up being? This is gonna be O of V + E. So and again, the way I think about this is if there weren't many edges at all, this would be dominated by the number of vertices. If there were tons of edges, this would be dominated by the number of edges, but you need to have both terms in there. Now what I want you to realize is that this is much more efficient if you have a sparse graph. So if you're comparing the amount of storage space required for an adjacency list versus the amount of space required for a matrix. For a sparse graph, easy, hands down, adjacency list is better. And if this were dense graphs, so there's tons and tons of edges. Well, there may be as many edges as essentially order V squared. Well, that just makes this basically as bad as a matrix not much worse. So in general, adjacency lists are use quite heavily, because of their space efficiency.