Help In Data Strucutre!

[hatemstar]

Part One
1. What does the following code do?

double problemRelPrime (int n)
{
int rel = 0, tot =0;
for( int i=1 ; i<=n ; i++ )
for( int j=i+1 ; j<=n ; j++ )
{
tot++;
if ( gcd(i, j) == 1 )
//gcd() calculates the greatest common divisor
rel++;
}
return (double) rel/tot;
}

2. Do the analysis of this program in term of big-Oh notation. Explain your result.
3. Check your analysis with the empirical running times (see table1).

N CPUTime (T) T/N2 T/N3 T/( N2logN)
100
200
300
400
500
600
700
800
900
1000
1500
2000
4000
Table1: Empirical running times
4. What is your conclusion?

Hint: To get the elapsed time in seconds, you may try the following:

time_t start,end;
time(start);
do_something();
time(end);
double dif = difftime(end, start);


Part Two

5. Write a program using a recursive function to calculate Fibonacci series. Do the empirical analysis of your program by calculating the execution time for n=10 to 100 with an increment of 10.
6. What is your conclusion?