In article <cu********@news3.newsguy.com>, Chris Torek

<no****@torek.net> wrote:

....

....

....

As you can see, an "N log N" algorithm does not bog down nearly as

fast as an "N squared" one -- even if it starts out a little slower,

it is faster once you have a significant number of items to process.

Big-O or "order" notation is useful for deciding how much data you

can stand to process. It completely ignores linear factors, however:

if routine A is O(n log n) and routine B is O(n log n), they have

the same order, but A can still run a million times faster than B

in all cases. So it is not the entire picture, just a very important

part of it.

Chris,

sorry for the very long delay in thanking you for your reply. thanks

very much for the answer, it was very helpful. i understood pretty much

all of what you said but i'm still a bit stuck on the details on how to

do the following exercise.

the exercise question is:

Prove an upper bound on the number of machine instructions required to

process M connections on N objects using the below programme. You may

assume, for example, that any C assignment statement always requires

less than c instructions, for some fixed constant c.

/* p1.3 quickunionweighted.c: a solution to the connectivity problem

with weighted tree */

#include <stdio.h>

#define N 10000

int main(void)

{

int i, j, p, q, id[N], sz[N];

for( i = 0; i < N; i++ )

id[i] = i, sz[i] = 1;

while( scanf("%d %d\n", &p, &q) == 2 ) {

// the FIND operation:

for( i = p; i != id[i]; i = id[i] ) ;

for( j = q; j != id[j]; j = id[j] ) ;

if( i == j ) continue;

// the UNION operation (inc. weighted tree maintenance):

if( sz[i] < sz[j] ) {

id[i] = j;

sz[j] += sz[i];

} else {

id[j] = i;

sz[i] += sz[j];

}

printf(" %d %d << new connection\n", p, q);

}

return 0;

}

so a formula that tells you the worst, most unlucky as it were, number

of instructions that'd have to be executed in order to complete the

above code (based on the M and N values) is required.

does the following course of action sound correct? taking the first

'for' loop from the FIND operation in the above code and using that as

an example would it go like this?:

each commented number represents how many instructions:

for( i = p; /* 2 - a read and a write */

i != id[i]; i = id[i] ) ; /* 4 * x - that is 2 reads and 2 writes

multiplied by the number of loops */

so say the number of loops was 10. 10*4 + 2 = 42.

then because the question says "You may assume, for example, that any C

assignment statement always requires less than c instructions, for some

fixed constant c." say i pick 5 for that (i'm a bit unsure on what

that quoted sentance means exactly)

so for this bit that 'for' line totals 42 * 5 = 210. so 210 machine

instructions for that 'for' loop being run 10 times.

obviously you'd need to work out how many times the for loop would get

run in the worst case, along with all the other parts of code, and

total all that up.

is that the rough idea of how to proceed to answer the exercise

question?

thanks, ben.