(1)Sort the following functions of n in the increasing order from left to right:
n,n2,n log n,log10 n,n10,2n,n3
(2) Specify the calculation cost for each loop below:
for( i=0; i<n; i++) sum++;
for( i=0; i<n; i++) for( j=0; j<n; j++) sum++;
for( i=0; i<n; i++) for( j=0; j< n*n;j++) sum++;
for( i=0; i<n; i++) for( j=0; j<i; j++) sum++;
(1) You can do the calculus for each function. However, it is better just to imagine the graph for each function, and to sort accordingly.
(2) We compare the calculation cost using the notation of order. For example, if the variable is n, the calculation costs of the order of n*n is denoted by O(n*n). In other words, for n=3, the calculation cost is 9. Think how the calculation cost (here number of the passes through the loop) changes when you change n.
Fill in the table with the execution times for the 4 loops in Problem 1 (2). Use the function gethrtime for the actual time measurement.
1. +----+---------+---------+---------+---------+---------+ | n | 2000000| 4000000| 6000000| 8000000| 10000000| +----+---------+---------+---------+---------+---------+ |time| | | | | | +----+---------+---------+---------+---------+---------+ 2. +----+---------+---------+---------+---------+---------+ | n | 2000| 4000| 6000| 8000| 10000| +----+---------+---------+---------+---------+---------+ |time| | | | | | +----+---------+---------+---------+---------+---------+ 3. +----+---------+---------+---------+---------+---------+ | n | 100| 200| 300| 400| 500| +----+---------+---------+---------+---------+---------+ |time| | | | | | +----+---------+---------+---------+---------+---------+ 4. +----+---------+---------+---------+---------+---------+ | n | 2000| 4000| 6000| 8000| 10000| +----+---------+---------+---------+---------+---------+ |time| | | | | | +----+---------+---------+---------+---------+---------+
This time, don't submit the program, but the results and a brief explanation.
In this problem, we tabulate the data from the calculation experiment. Confirm that the calculation cost in Problem 1 (2) and the results of experiment correspond. For example, if you change n=2000000 -> n=10000000, i.e. by factor 5, what is the increase factor in the calculation time?
Here we use the function gethrtime. It measures time in the units of nanoseconds. Refer to the following example for further details.
#include <stdio.h>
#include <sys/time.h>
int main(){
int i,n,sum;
hrtime_t start,finish;
printf("n= ");
scanf("%d",&n);
start=gethrtime(); /* start measurement */
sum=0;
for( i=0; i<n; i++) sum++;
finish=gethrtime(); /* stop measurement */
printf("time: %f seconds.\n", (double)(finish-start)/NANOSEC);
return 0;
}
Use a tool (xmgrace) for outputting the results of Problem 2 (4) into a plot. The form is as follows.
Value of n
from 500 to 10 000 with the mesh step 500.
Example: % ./a.out > ex05-3.dat % cat ex05-3.dat 500 0.006423 1000 0.026013 1500 0.058152 2000 0.103227 2500 0.162220 3000 0.231876 3500 0.316341 4000 0.422904 4500 0.525531 5000 0.645877 5500 0.780517 6000 0.933092 6500 1.095727 7000 1.267396 7500 1.455250 8000 1.655440 8500 1.873892 9000 2.096666 9500 2.342806 10000 2.582010 % xmgrace ex05-3.dat &
Making one experiment a function (time measurement start, loop execution, time measurement end) , n has the role of variable.
Using xmgrace for displaying the function results in a graph, confirm the result with the predicted calculation costs.
See literacy handout about usage of xmgrece.