So the first claim is that, the non-trivial work of this algorithm all

takes place via heap operations. That is, it suffices to just count the

number of heap operations, each of which we know is done in logarithmic time.

Okay, so let's count up all of the heap

operations. One thing we already talked about,

but I'll mention it here again for completeness is we do a bunch of inserts

just to initialize the heap in a pre-processing step.

So after we initialize, we move on to the main while loop.

Remember, there's exactly N minus one iterations of that while loop.

And in each one, we extract min exactly once.

So these were the easy steps. What you should be concerned about.

Are, the, heap operations, the deletions and re-insertions that are triggered by

needing to decrease the key avertices that are not in X.

Indeed, in a single iteration of Prim's algorithm, in a single move of a vertex

inside of capital X, can necessitate a large number of heap operations.

So, it's important to think, to count these operations in the right way, namely

in a edge-centric manner and the claim is that a single edge of the graph is only

going to trigger a single decrease key pair of.

Operations a single insertion deletion combo.

We can even pinpoint the moment in time at which we're going to have this inser,

this deletion and reinsertion. It's going to be when the first of the

endpoints, so either V or W, the first iteration at which one of those gets

sucked into the left-hand side capital X, that's going to trigger the

insert-delete, potentially for the other endpoint.

When the second endpoint gets sucked into the left-hand side, you don't care,

because the other endpoint has already been taken out of the heap,

there's no need to maintain its key. So that means that the number of heap

operations is almost twice the number of vertices plus almost twice the number of

edges. We're again going to use this fact that

the input graph is connected and therefore the number of edges is

asymptotically at least the number of vertices.

So we can say that the number of heap operations is at most a constant factor

times the number of edges, M. As we've discussed every heap operation

runs in time logarithmic in the number of objects in the heap so that's going to be

Log N in this case so we get an overall running time of O of M times Log N.

So this is now a quite impressive running time for the really quite non-trivial

minimum cost spanning tree problem. Of course we'd love to do even better.

If we could shave off the Log N factor and be linear in the input, that would be

even more awesome. But we gotta feel pretty good about this

running time. Right?

This is only a Log N factor slower than what it takes to read the input.

This is the same kind of running time we're getting for sorting.

So this actually puts the minimum spanning tree problem into the class of

four free primitives. If you have a graph and it fits in the

main memory of your computer, this algorithm is so fast.

Maybe you don't even know why you care about the minimum spinning shaver graph.

Why not do it? It's basically cost-less.

That's how fast this algorithm is.