title: Running Time of Graph Algorithms
body: <p>I am a bit confused on <strong>how to determine the running time of graph algorithms</strong>.  That is, determining an estimated running time using the number of vertices (n) and the number of edges (m).  Does someone mind explaining to me where my logic is flawed, and explain how to properly analyze these and find the running times?</p>
  
  <p>Here is an example graph algorithm:</p>
  
  <pre><code>//input: Directed graph G represented by adjacency lists.
  Func1(G) {
  k = 0;
  foreach vertex vi in V(G) do
      foreach directed edge (vi, vj) incident on vi do
      k=k+1; //just some constant time operation
      end
  end
  return(k);
  }
  </code></pre>
  
  <p>The running time of this graph algorithm is given as O(m+n) in BigO notation.  Now here is my question:</p>
  
  <p>Just looking at this algorithm for a quick mental analysis, why isn't the running time instead equal to O(n*m)?  The outer loop runs n times, in other words once for each vertex.  Now the inner loop runs once for each edge, m times.  Thus I thought that both loops together would run n*m times.</p>
  
  <p>One last less trivial question is, how would the algorithm running time change should the input be given as an adjacency matrix, rather than an adjacency list?</p>
  
  <p>I cannot find a good resource for this online, there are no clear and concise examples covering this topic.  Would really appreciate if someone can help me create one :)</p>