I know from the book by Neapolitan that for any algorithm input size is defined as the number of bits to encode the input. In graph algorithms, the input size is defined as $|V(G)| + |E(G)|$ for the input graph $G$. On the other hand, we save graphs in computers by their either adjacency lists or adjacency matrices which are of size $2|E(G)|$ and $|V(G)|^{2}$. So how is the input size $|V(G)| + |E(G)|$?


1 Answer 1


The size of adjacency list representation is $\Theta(|E(G)| + |V(G)|)$, and not $\Theta(|E(G)|)$. For example, consider a graph with $n$ vertices and $0$ edges. The adjacency list corresponding to each vertex is empty. But storing the null pointer requires constant space for each vertex. Therefore, the size of the adjacency lists is $|V(G)|$ here.

  • $\begingroup$ So if we want to compute the (almost) exact size of an undirected graph $G$ which is in adjacency list representation, it's $|V(G)| + 2|E(G)|$. Right? $\endgroup$
    – Emad
    Commented Sep 21, 2021 at 5:12
  • $\begingroup$ @Emad For an undirected graph: yes. For a directed graph, precisely it is $|V(G)| + |E(G)|$ . Although it is better to say $\Theta(|V(G)| + |E(G)|)$ for both. $\endgroup$ Commented Sep 21, 2021 at 5:22
  • $\begingroup$ And for the adjacency matrix representation, it's $\Theta(|V(G)|^{2})$ for both types? $\endgroup$
    – Emad
    Commented Sep 21, 2021 at 5:29
  • $\begingroup$ @Emad right. Always. $\endgroup$ Commented Sep 21, 2021 at 5:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.