Space complexity of Adjacency List representation of Graph
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
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).
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