Howdy, Stranger!

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


Deriving time complexity equations from psuedocode

damo87damo87 Member Posts: 1
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.