title: Why are operations in an adjacency list O(|E|/|V|)$?
body: <p>I'm studying for an exam I have soon. A chart provided to me has the following algorithmic complexities summarized for an adjacency list for a graph with N nodes and E edges.</p>
  
  <ul>
  <li><p>Find edge - O(E/N)</p></li>
  <li><p>Insert edge - O(E/N)</p></li>
  <li><p>Delete edge - O(E/N)</p></li>
  <li><p>Enumerate edges for node - O(E/N)</p></li>
  </ul>
  
  <p>I understand what an adjacency list is - we store the vertices adjacent to each vertex by using an array of lists. But why are these operations O(E/N)? It seems to me like, if we took a graph in which every possible edge is drawn (e.g., we have n(n - 1)/2 edges if the graph is undirected), then each list in the array would have N - 1 entries to store every other node</p>
  
  <p>This, in my mind, would be the "worst case," wouldn't it? I don't understand how the ratio of edges to nodes is being obtained. </p>
  
  <p>Can someone please explain?</p>