1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

The time complexity is $O(n^2)$ because $O(n\cdot(n-1)) = O(n^2)$

The big-O notation is showing the worst-case performance of one algorithm, it is not showing the exact number of steps the algorithm will make, but only its overall complexity

For example $$O(2n) = O(n)\\O(3n) = O(n)\\O(\frac{n}{2}) = O(n)\\O(2n^2) = O(n^2)$$

$\endgroup$
0
$\begingroup$

In prim's algorithm for every vertex you have to search for all the adjacent vertices which can be O(n) in worst case and search for minimum among them takes O(n) time. So TC for one vertex will be O(n)+O(n)=O(n). For n vertices TC will be n*O(n)=O(n^2)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.