The complexity of Prims Algorithm using Array and Adjacency List is:
V^2 + V + 2E + E = O(V^2)
But, I can't recall why E
.
The complexity using an adjacency list structure for graph representation, and an array for a priority queue, is Θ(|V|2 + |E|). For graphs without parallel edges, this is Θ(|V|2).
Prim's algorithm works in |V| iterations, growing a tree starting with size 1 and ending with size |V|. Say at some iteration, vertex v is added to the tree, and lete E(v) be the edges emanating from v. For each such edge, we can find the neighbor in the array, and update the lightest distance from some vertex in the current tree to it. Finding the vertex v takes time Θ(|V|), as we must scan the array to find the minimum (it's an inefficient implementation of a priority queue).
Altogether, each edge is accessed once in each direction (hence Θ(|E|), and each of the |V| iteration does a Θ(|V|) scan on the array.
Note that for your expression in the question, V^2+V+2E+E, it's important to recall that the context is a consideration of orders of growth. Hence there's not much meaning to 2E (what does the 2 stand for? iterating twice over the edges? The number of CPU instructions per edge?) or indeed to 2E + E. These are just vague shorthand notations used sometimes to indicate the various stages in the algorithm.