Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Deriving time complexity equations from psuedocode

Hi, can anyone explain to me how to derive a time complexity equation from psuedo-code? I've read alot of notes about how it works but its still not clicking with me. I need to compare Kruskal's and Prim's algorithms.

Is it somthing like .. a for-loop = N, a nested for-loop = N^2, a function call = N, an if-statement = 1? not really sure what each statment translates to in terms of N.. does anyone know of any kind of conversion table?

Here's an example of one of the psuedocodes i need to analyse:

Algorithm Kruskal(E, T: Set; Cost:matrix; n, mincost :integer) {
Forest : Array[1..n] of VertexList;
Edgelist : Heap;
for (i= 1; i <= n ; i++)
Insert(Forest, i); // make initial Forest
MakeHeap(Edgelist, e); // order edges by least cost

i=0; mincost =0; // start cost

while ((i<n-1) && (Not Empty(Edgelist)) ) {
(u,v) = Edgelist[1]; Edgelist[1] = Edgelist[e]; e:= e-1; // take an edge
FixHeap(Edgelist, e, 1); // find next min cost edge
j = FindVertex(Forest, u); k= FindVertex(Forest, v); // locate vertices

if (j != k) { // if edge does not form cycle
i= i+1; T[i] = ( u,v); // add edge to spanning tree
mincost = mincost + Cost[u,v]; // update total cost
Merge(Forest, j, k) // update forest
}
}
if (i != n-1) print(
Sign In or Register to comment.