Suppose you implement prims algo by adjacency matrix, Then after selecting the minimum vertex, you ll have to go through V entries corresponding to that vertex in matrix and select the minimum. So on, you do this for V vertices. So, complexity becomes O(V2)