How much storage is needed to represent a simple graph with n vertices and m edges using.
Here one thing is not mentioned which is graph is directed or undirected graph
For directed Graph (n= vertices, m=edges)
1) O(m+n) for a dense graph m>> n, m$\simeq n^{2}$ thus O(n$^{2}$)
2) O(n*n) = O(n$^{2}$)
3) O(m*n) for dense graph m$\simeq n^{2}$ O(n$^{3}$)
For undirected graph (n= vertices, m=edges)
1) O(n+2*m) for a dense graph m>> n, m$\simeq n^{2}$ thus O(n$^{2}$)
2) O(n*n) = O(n$^{2}$)
3) O(m*n) for dense graph m$\simeq n^{2}$ O(n$^{3}$)
Space complexity wise it doesn't make any difference in directed vs undirected but if we go for deeper analysis extra cost is associated with each method