# Input size in graph algorithms

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)|$$?

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.
• 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?
• @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. Commented Sep 21, 2021 at 5:22
• And for the adjacency matrix representation, it's $\Theta(|V(G)|^{2})$ for both types?