470,822 Members | 1,369 Online

# math question in c algorithm book help please

hello,
i'm following an algorithm book and am stuck on an early excersise in
it, not because of the c programming side of it or even the algorithm
side of it, i don't think, but because of maths. i don't really
understand what is expected, or really what the question means. could
anyone explain what the question's after please?
any help much appreciated.
thanks, ben.

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;
}
Nov 14 '05 #1
2 1944 In article <06******************@x.x>, ben <x@x.x> wrote:
i'm following an algorithm book and am stuck on an early excersise in
it, not because of the c programming side of it or even the algorithm
side of it, i don't think, but because of maths. i don't really
understand what is expected, or really what the question means. could
anyone explain what the question's after please? 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.

The question is about algorithm time complexity. For instance,
sorting operations are typically O(N log N) or O(N * N), where N
is the number of items being sorted. Roughly speaking, that tells
you how long it takes to sort 10 items, vs 15000, vs a million
(or indeed any other number N).

Suppose the algorithm is "order n-squared", and it takes about a
millisecond to sort 10 items. Then:

10*10 = 100 => 1.00 millisecond
1500*1500 = 2250000 => 22500.00 milliseconds (or 22.5 seconds)
1mil*1mil = 1e12 => 1e12 milliseconds
= 1e9 seconds
= ~11574 days
= ~31.7 years

Hence, sorting a million items with this code is probably not a
good idea.

On the other hand, suppose you find an algorithm that is "order n
log n" (log2, in this case, although it does not matter in big-O
notation because log10 X / log2 X is a constant). Suppose it is
about three times slower for ten items, taking just over 3 milliseconds
(I am doing this to make the math easier). Then:

10 * log2 10 = 33.2 => 3.32 milliseconds
1500 * log2 1500 = 15826.1 => 1582.61 milliseconds (~1.6 seconds)
1mil * log2 1mil = 19931568.6 => 1993156.86 milliseconds
= ~1993 seconds
= ~33.2 minutes

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.

General algorithm questions (including "is this O(whatever)") mostly
belong in comp.programming.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
Reading email is like searching for food in the garbage, thanks to spammers.
Nov 14 '05 #2
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.
Nov 14 '05 #3

### This discussion thread is closed

Replies have been disabled for this discussion.