Line Count Of A Function

Question

Take the following function and other code, and code it up so as it runs, it calculates its own line count.

typedef double Matrix[100][100];

void multiply(Matrix A, Matrix B, Matrix C, int n)
{
     //n is the actual matrix order
     for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
        {
            C[i][j] = 0;
            for (int k = 0; k < n; ++k)
                 C[i][j] += A[i][k] * B[k][j];
        } 
}

So I have a hard time understanding what I am supposed to do. I'm not sure what a line count is for this particular problem. If anybody can just clarify what I need to do, that would be a big help, That's all I ask.

What I'm being asked: Write a main that initializes an int variable lc to zero, and inputs n to size the matrices. Pass lc by reference to the multiply function. Have it come back as the number of lines of code executed, and print this out together with n. Also you should initialize matrices A and B to be Hilbert matrices (the i-jth entry being 1.0 / (i + j + 1)). Test it for n = 3 so your product will be the 3x3 Hilbert matrix squared(just to make sure your code works). Then, set it up to run twice: once with n = 50, and once again for n = 100. Note the time for n = 100, it should be around 8 times as long as it took for n = 50.

Answer 1

The question says "code it up so as it runs, it calculates its own line count" which means "instrument the code so that every line of code gets counted"

If you count the number of statements executed in a for loop from 0 to 9 there will be 1 for the for loop initializer, 11 for the loop comparison (because you compare once for the index 10 to realize that the loop is over), 10 for the loop increment and 10 for each statement of content in the loop. That totals 32 which is proportional to 10 (the size of the loop) so the complexity is O(N)

If you count the number of statements executed in a nested for loop where both loops run from 0 to 9 there will be 1 for the outer loop initializer, 11 for the outer loop comparison (because you compare once for the index 10 to realize that the loop is over), 10 for the outer loop increment and 10 for each statement of content in the outer loop: 10*1 for the inner loop initializer, 10*11 for in the inner loop comparison, 10*10 for the inner loop increment and 10*10 for each statement of content in the loop. That totals 352 which is proportional to 10^2 (the square of the size of the loop) so the complexity is O(N^2)

And since your multiply function has three loops from 0 to n the complexity would be O(n^3)

Here is how I would instrument the code to count the statements:

#include <stdio.h>
#include <math.h>

#define N 10
int count=0;

void simpleloop()
{
  count=0;
  ++count;  int sum=0;               // 1   for this line
  ++count;  for(int i=0;             // 1   for this line
  ++count,      i<N;                 // N+1 for this line (i=0 through i=N   inclusive)
  ++count,      ++i)                 // N   for this line (i=0 through i=N-1 inclusive)
            {
  ++count;    sum+=i;                // N   for this line (i=0 through i=N-1 inclusive)
            }
  ++count;  printf("sum=%d\n",sum);  // 1   for this line
}

void nestedloop()
{
  count=0;
  ++count;  int sum=0;               // 1       for this line
  ++count;  for(int i=0;             // 1       for this line
  ++count,      i<N;                 // N+1     for this line (i=0 through i=N   inclusive)
  ++count,      ++i)                 // N       for this line (i=0 through i=N-1 inclusive)
            {
  ++count;    for(int j=0;           // N       for this line
  ++count,        j<N;               // N*(N+1) for this line N*(j=0 through j=N   inclusive)
  ++count,        ++j)               // N*N     for this line N*(j=0 through j=N-1 inclusive)
              {
  ++count;      sum+=i*N+j;          // N*N     for this line N*(j=0 through j=N-1 inclusive)
              }
            }
  ++count;  printf("sum=%d\n",sum);  // 1       for this line
}

typedef double Matrix[100][100];

void multiply(Matrix A, Matrix B, Matrix C, int n)
{
  count=0;
            // n is the actual matrix order
  ++count;  for (int i = 0;                      // 1         for this line
  ++count,       i < n;                          // n+1       for this line
  ++count,       ++i)                            // n         for this line
            {
  ++count;    for (int j = 0;                    // n         for this line
  ++count,         j < n;                        // n*(n+1)   for this line
  ++count,         ++j)                          // n*n       for this line
              {
  ++count;      C[i][j] = 0;                     // n*n       for this line
  ++count;      for (int k = 0;                  // n*n       for this line
  ++count,           k < n;                      // n*n*(n+1) for this line
  ++count,           ++k)                        // n*n*n     for this line
                {
  ++count;        C[i][j] += A[i][k] * B[k][j];  // n*n*n     for this line
                }
              }
            }
}

int main()
{
  printf("simpleloop:\n");
  simpleloop();
  printf("count=%d O(N^%d)\n\n",count,(int)log10(count/N)+1); // total counts = 3N + 4 -> O(N)

  printf("nestedloop:\n");
  nestedloop();
  printf("count=%d O(N^%d)\n\n",count,(int)log10(count/N)+1); // total counts = 3N^2 + 4N + 4 -> O(N^2)

  Matrix A={},B={},C={};
  printf("multiply:\n");
  multiply(A,B,C,N);
  printf("count=%d O(N^%d)\n\n",count,(int)log10(count/N)+1); // total counts = 3N^3 + 5N^2 + 4N + 2 -> O(N^3)

  return 0;
}

Counting the statements gives a slightly different count than counting the lines because a for loop has three statements plus the content of the loop. I think it is better measure of the number of things that happen but it isn't exactly what your question asked for so if you really want lines you will have to remove the count from the loop comparison and loop increments. The complexity will stay the same.