How should complexity measures be interpreted?
One has always to keep in mind that whatever the quality of the instrumentation tool, the outcoming results should be handled with care. Instrumenting non-optimized source code can provide disastrous profiling results, which are orders of magnitude worse than profiling results obtained from optimized code. As a simple example, the reader is referred to Table 1. The first column shows source code for an iterative calculation without optimization. The second column corresponds to the same functionality, but calculated in an optimized way for memory accesses, by introducing registers instead of external memory accesses. In the third column, the iterative calculation scheme has been transformed into a closed-form analytical calculation formula. Clearly, the number of arithmetic operations and memory accesses can vary drastically between the different versions.
