Deriving time complexity equations from psuedo-code

[damo87]

Hi, hopefully this is the right sort of forum to be asking this in! 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(‘no spanning tree’);


any help here would be greatly appriciated, thanks!

[TheCPUWizard]

You count how many times an operation is performed based on the size of the data. It is that simple...

for (int i=-0; i<n; ++i) {.....}

the code inside the loop will execute N times....

for (int i=-0; i<n; ++i) for (int j=0;j<n;++j) {.....}

the code inside the loop will execute N^2 times.

If there are multiple parts [e.g. f some are O(1), some are O(N) and some are O(N^2) ], then the overall algroithm has a complexity of the highest order component.

Walk through the code you posted (WHY didnt you use code tags - have you forgotten what you read in the FAQ's), and stert counting the number of comparisions and assignments that occur for different input sizes.....