B
ben
hello,
i'm trying to answer a "prove an upper bound on the number of machine
instructions required to process M connections on N objects" exercise
from an algorithms book. i don't understand a very basic detail of how
i should go about answering the exercise. here's a simplified example
question and example programme to hopefully get at what i'd like to
know:
Prove an upper bound on the number of machine instructions required to
process 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.
/* a very simple and silly example "algorithm" */
#include <stdio.h>
#define N 10000
int main(void)
{
int n = 0;
int x[3] = { 1, 4, 9 };
long unsigned total = 0;
while( n < N ) {
total += x[ n % 3 ];
n++;
}
printf("%lu\n", total);
return 0;
}
i know the "upper bound" aspect of the question isn't particularly
meaningful with this programme, as after the value of N has been
decided there's nothing variable about the number of times the loop is
run -- upper and lower bound the same -- one fixed, by N, value. but i
wanted to leave the question as unchanged as possible.
to answer that exercise, is it a case of assigning a certain number of
machine instructions to each and every C statement, or operation, in
the loop, adding those up, and then multiplying that by the number of
loops?
it's the "You may assume, for example, that any C assignment statement
always requires less than c instructions, for some fixed constant c."
part i'm unsure on.
how exactly would you go about answering the above exercise (ignoring
the sillyness part of it)?
thanks, ben.
i'm trying to answer a "prove an upper bound on the number of machine
instructions required to process M connections on N objects" exercise
from an algorithms book. i don't understand a very basic detail of how
i should go about answering the exercise. here's a simplified example
question and example programme to hopefully get at what i'd like to
know:
Prove an upper bound on the number of machine instructions required to
process 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.
/* a very simple and silly example "algorithm" */
#include <stdio.h>
#define N 10000
int main(void)
{
int n = 0;
int x[3] = { 1, 4, 9 };
long unsigned total = 0;
while( n < N ) {
total += x[ n % 3 ];
n++;
}
printf("%lu\n", total);
return 0;
}
i know the "upper bound" aspect of the question isn't particularly
meaningful with this programme, as after the value of N has been
decided there's nothing variable about the number of times the loop is
run -- upper and lower bound the same -- one fixed, by N, value. but i
wanted to leave the question as unchanged as possible.
to answer that exercise, is it a case of assigning a certain number of
machine instructions to each and every C statement, or operation, in
the loop, adding those up, and then multiplying that by the number of
loops?
it's the "You may assume, for example, that any C assignment statement
always requires less than c instructions, for some fixed constant c."
part i'm unsure on.
how exactly would you go about answering the above exercise (ignoring
the sillyness part of it)?
thanks, ben.