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.
