2
int maxValue = m[0][0];         
for (int i = 0; i < N; i++) 
{               
    for (int j = 0; j < N; j++) 
    {                    
        if ( m[i][j] >maxValue )        
        {                 
            maxValue = m[i][j];     
        }                     
    }                    
}                   
cout<<maxValue<<endl;           

int sum = 0;                
for (int i = 0; i < N; i++)     
{                   
    for (int j = 0; j < N; j++)     
    {                    
        sum = sum + m[i][j];            
    }                    
} 
cout<< sum <<endl;

For the above code if we draw a flow graph like this flow graph basic independent paths would be following six
Path 1: 1 2 3 10 11 12 13 19
Path 2: 1 2 3 10 11 12 13 14 15 18 13 19
Path 3: 1 2 3 10 11 12 13 14 15 16 17 15 18 13 19
Path 4: 1 2 3 4 5 9 3 10 11 12 13 19
Path 5: 1 2 3 4 5 6 8 5 9 3 10 11 12 13 14 15 16 17 15 18 13 19
Path 6: 1 2 3 4 5 6 7 8 5 9 3 10 11 12 13 14 15 16 17 15 18 13 19

So the question here is according to the given code path 2, 3, 4 can not be tested (Note the "N" in loops). So is it okay not to have a actual execution path as given in the basic set?... or according to macabe complexity metric do we have to change the code given above. Because a tutor of mine said we have to change the code also he said that there are unstructured loops so we have to change the code. (I don't see an unstructured loop as well) But my feeling is, if we change the code actual output may differ to expected output. So please someone explain this

1 Answer 1

7

1) McCabe's complexity can be calculated as the number of decision points + 1. In your case there are 5 decision points (nodes 3, 5, 6, 13 and 15) meaning that the McCabe complexity of the code fragment is 5+1 = 6. 6 is by no means too high in terms of McCabe complexity: one could, of course, still argue that it is too high given the functionality the implementation has to provide.

2) McCabe's complexity is related to testability of a method/procedure but not to testability of a specific path. Paths can be feasible (= there exist values of the variables that force the execution through this path) or not, but McCabe's complexity is happily unaware of such complications. If you really want to look into feasibility of paths keep in mind that the problem in general is undecidable but many practical data flow analysis algorithms are available.

3) if we change the code actual output may differ to expected output Of course, you cannot introduce an arbitrary change and hope that the results will be the same. However, and, this is probably what your tutor intended, there is a way of restructuring your code such that the output produced remains the same, and the McCabe's complexity goes down. Think, e.g., on whether you really need to separate the tasks of calculating the maximum and the sum.

2
  • 3
    McCabe's complexity isn't defined as number of decisions points plus one, at least not by McCabe. There's a theorem that proves his definition is equivalent to decision points plus 1, which is a lot easier to compute :-}
    – Ira Baxter
    May 10, 2012 at 12:09
  • Right ;-) Sorry, for the confusion, and, of course, the #decision points + 1 holds only for structured programming. I'll update the answer. May 10, 2012 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.