Algorithms and Data Structures
Excercise 5
Calculation Cost

In this exercise, we will study the calculation cost (complexity) of algorithms. This is an outstanding criterion for evaluating different algorithms.
Problem 1PostScript for printing

(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:

  1. for( i=0; i<n; i++) sum++;
    
  2. for( i=0; i<n; i++)
      for( j=0; j<n; j++) sum++;
    
  3. for( i=0; i<n; i++)
      for( j=0; j< n*n;j++) sum++;
    
  4. 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.

Problem 2

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;
}
Problem 3

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.


The original Japanese document was written by Naoki Wakamatsu
This translation document was written by Kenichi Maezu <m5061121@u-aizu.ac.jp>
and Hajime Matsui <m5061122@u-aizu.ac.jp> and checked by L. Pichl.