Search code examples
calgorithm

Calculate Frequency Count for each statement in the following C code

How do I calculate the frequency count of each statement (i.e. the number of time each statement gets read/executed) in the following C code.
The frequency count of each statement must be written in terms of 'n'. 

for(i=1;i<=n;i++)  
     for(j=1;j<=i;j++)  
          for(k=1;k<=j;k++)
                x=x+1;
Solution

  • See this way, at maximum ,

    for(i=1;i<=n;i++)  // Executes n times
     for(j=1;j<=i;j++)  // Executes i times for every i -> (1 + 2 + 3 + 4....n)
          for(k=1;k<=j;k++) // Executes j times for every i,j ---> (1+(1+2)+(1+2+3).....(1+2+3...n)) 
                x=x+1; // Executes every time for every i,j,k ---> (1+(1+2)+.....(1+2+3...n)

 So, you can figure out from this that :

    n + n*(n+1)/2 + (n+(n-1)2+(n-2)3.....(1)n)*2 ... = n + n(n+1)/2+ ((n)(n+1)(n+2)/6)*2 .. This is your answer.