Pregunta

There is this Prim's algorithm I am studying, the time complexity of which is $O(n^2)$ (in the adjacency matrix).

As far as I have understood,that is because we have to ckeck all the nodes per every node, that is, when checking the first node's best edge, we have to check edges from the current node to all other nodes. That makes $(n-1)$ edges at most. We check this for all nodes, so it would be n*(n-1) edges to check at most.

So why is the time complexity $O(n^2)$?

In addition, why don't we consider the edges which create a loop and why don't we ommit them in the algorithm? Does that make any difference in the time complexity?

No hay solución correcta

Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange
scroll top