title: Why is the time complexity of Dijkstra O((V + E) logV)
body: <p>I was reading about worst case time complexity for the Dijkstra algorithm using binary heap (the graph being represented as adjacency list).</p>
  <p>According to wikipedia (<a href="https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Running_time" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Running_time</a>) and various stackoverflow questions, this is <code>O((V + E) logV)</code> where E - number of edges, V - number of vertices. However I found no explanation as to why it can't be done in <code>O(V + E logV)</code>.</p>
  <blockquote>
  <p>With a self-balancing binary search tree or binary heap, the algorithm requires <code>Θ((E+V) logV)</code> time in the worst case</p>
  </blockquote>
  <p>In case E &gt;= V, the complexity reduces to <code>O(E logV)</code> anyway. Otherwise, we have <code>O(E)</code> vertices in the same connected component as the start vertex (and the algorithm ends once we get to them). On each iteration we obtain one of these vertices, taking <code>O(logV)</code> time to remove it from the heap.
  Each update of the distance to a connected vertex takes <code>O(logV)</code> and the number of these updates is bound by the number of edges E so in total we do <code>O(E)</code> such updates. Adding <code>O(V)</code> time for initializing distances, we get final complexity <code>O(V + E logV)</code>.</p>
  <p>Where am I wrong?</p>