Howdy, Stranger!

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


Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Deriving time complexity equations from psuedocode

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