16

I read here that for Undirected graph the space complexity is O(V + E) when represented as a adjacency list where V and E are number of vertex and edges respectively.

My analysis is, for a completely connected graph each entry of the list will contain |V|-1 nodes then we have a total of |V| vertices hence, the space complexity seems to be O(|V|*|V-1|) which seems O(|V|^2) what I am missing here?

CodeYogi
  • 1,352
  • 1
  • 18
  • 41

3 Answers3

19

You analysis is correct for a completely connected graph. However, note that for a completely connected graph the number of edges E is O(V^2) itself, so the notation O(V+E) for the space complexity is still correct too.

However, the real advantage of adjacency lists is that they allow to save space for the graphs that are not really densely connected. If the number of edges is much smaller than V^2, then adjacency lists will take O(V+E), and not O(V^2) space.

Note that when you talk about O-notation, you usually have three types of variables (or, well, input data in general). First is the variables dependence on which you are studying; second are those variables that are considered constant; and third are kind of "free" variables, which you usually assume to take the worst-case values. For example, if you talk about sorting an array of N integers, you usually want to study the dependence of sorting time on N, so N is of the first kind. You usually consider the size of integers to be constant (that is, you assume that comparison is done in O(1), etc.), and you usually consider the particular array elements to be "free", that is, you study that runtime for the worst possible combination of particular array elements. However, you might want to study the same algorithm from a different point of view, and it will lead to a different expression of complexity.

For graph algorithms, you can, of course, consider the number of vertices V to be of first kind, and the number of edges to be the third kind, and study the space complexity for given V and for the worst-case number of edges. Then you indeed get O(V^2). But it is also often useful to treat both V and E as variables of the first type, thus getting the complexity expression as O(V+E).

Petr
  • 9,812
  • 1
  • 28
  • 52
  • I am doing something wrong in my analysis here, I have multiplied the two variable `O(|V|*|V-1|)` what mistake I am making? – CodeYogi Nov 03 '15 at 13:48
  • @CodeYogi, you are not wrong for the case when you study the dependence only on `V`. But if you study the dependence on both `V` and `E`, a better complexity can be proved, and you are wrong in assuming _complete graph_, while not every graph is complete. – Petr Nov 03 '15 at 13:49
  • Ya, I chose complete graph because its what we are told while studying the running time to chose the worst possible scenario. But I think I need some more reading to wrap my head around your explanation :) – CodeYogi Nov 03 '15 at 13:51
  • @CodeYogi, yes, but before jumping to the worst case, you need to assume which variables you study the dependence on and which you completely fix. For example, for sorting obviously the bigger `N` the worse the case is, but obviously you do not jump to the infinite `N` as the worst-case. – Petr Nov 03 '15 at 13:53
  • If its not idiotic can you please explain [this](http://stackoverflow.com/a/11468717/4260745), I am confused why we are adding complexities here as AFAIK the nested loops mean we need to multiply steps and not add them. What I mean is v1*incident_edges and so on. – CodeYogi Nov 03 '15 at 14:16
  • @CodeYogi, I find the formula in the question you linked quite misleading. I guess you'd better find a good book on this. – Petr Nov 03 '15 at 14:26
3

Size of array is |V| (|V| is the number of nodes). These |V| lists each have the degree which is denoted by deg(v). We add up all those, and apply the Handshaking Lemma. ∑deg(v)=2|E| .

So, you have |V| references (to |V| lists) plus the number of nodes in the lists, which never exceeds 2|E| . Therefore, the worst-case space (storage) complexity of an adjacency list is O(|V|+2|E|)= O(|V|+|E|).

Hope this helps

Tanmey Rawal
  • 181
  • 1
  • 7
2

according to u r logic, total space = O(v^2-v) as total no. of connections(E) = v^2 - v, space = O(E). even I used to think the same, But if you have total no. of connections(E) much lesser than no. of vertices(V), lets say out of 10 people (V=10), only 2 knows each other, therefore (E=2) then according to your logic space = O(E) = O(2) but we in actual we have to allocate much larger space which is space = O(V+E) = O(V+2) = O(V) that's why, space = O(V+E), this will work if V > E or E > V

krishna sunder
  • 31
  • 3