Complexity
A function might be simple or it might be complex. And while a simple function might be obviously correct, a complex function might need hundreds of tests to demonstrate its correctness.
There is a well-known measure of complexity known as “cyclomatic complexity” and this is the number of linearly independent paths through a function. Without going into details, we can compute this complexity using the following formula:
complexity = E − N + 2
where
E = the number of edges in the control flow graph
N = the number of nodes in the control flow graph
Clearly, the more complex a subprogram the more likely a programmer will make mistakes and the less likely that tests will find them. The Software Engineering Institute relates complexity to risk as follows:
| Complexity | Risk |
| 1-10 | A simple function, without much risk |
| 11-20 | more complex, moderate risk |
| 21-50 | complex, high risk |
| greater than 50 | untestable function, very high risk |
Risk is important. In a mission-critical system any level of risk is unwelcome. This is obvious. But we cannot write complex software where all functions have a complexity equal to one. We have to be able to reduce the risk with complex functions, say with a complexity up to 20.
We do this using static analysis. Unfortunately some of the meaning of a function only becomes clear at run time (operations in loops for example) so static analysis is limited in what it can do. However it does find the most common errors.
The following table shows an improvement in risk. Risk has been reduced because the static analyzer has detected faults and blocked the development path.
The XGC flow analyzer generates a warning where complexity is greater then 10. And it reports an error where complexity is greater than 20.
| Complexity | Risk with Static Analysis |
| 1-10 | A simple function, without much risk |
| 11-20 | more complex, without much risk |
| 21-50 | complex, high risk |
| greater than 50 | untestable function, very high risk |
From the point of view of testing the complexity number is also the minimum number of tests required for 100 percent coverage.
—-
So what is linearly independent?
According to Wikipedia: “A set of vectors is said to be linearly dependent if one of the vectors in the set can be defined as a linear combination of the other vectors. If no vector in the set can be written in this way, then the vectors are said to be linearly independent.“