Empirical Measures

From

Empirical analysis of a program is a factual enquiry carried out by recording what is observed or measured from actual run-time behavior of a program. Two of the more common empirical measures of program behavior are actual clock time and operations counting. Measuring clock time usually involves adding calls to the system clock at the begining and end of the process or function that you wish to measure. Measuring operations frequency commonly include counting comparisons, counting assignments (memory writes), and counting the number of times the inner most code in a loop is executed.

Asymptotic measures are "analytical" meaning that we look at the algorithm and deduce it's behavior. Empirical measures are situational observations; we measure real behavior for a specific situation. They are complimentary to each other; empirical measures should validate our analytical view of program behavior.

Empirical counting of operations

Adding automated counting into code is a realatively easy task:

1. Create one or more variables to function as counters and initialize them
2. Identify the appropriate place in your code to increment the counter so that you are counting the behavior that you are interested in
3. Output the counter after the task has finished

As an example, here is a function with 2 very simple nested loops; Analytically, I can see that each loop control is linear with N, but as it is nested, that puts this code into O( N^2 ). Now I want to empirically verify this with a counter, so I create and initialize the counter, increment it in the inner loop, and finally output the value after the loops have completed.

    FUNCTION nestedLoops( n )
        LET counter1 = 0  //This is the counter to measure execution work    
        do some initialization work
	FOR i FROM 0 TO n BY 1
            FOR j FROM y TO 0 BY -1
                Let counter1 = counter1 + 1 //Increment the counter
    		do the functions work
            ENDFOR
        ENDFOR
        output( counter1 )  //Somehow record or output the counter
        RETURN work
    ENDFUNCTION	

Finally, you would choose a range of values for N to test this code against and observe the recorded values of your counter. The values of the counter should validate the analysis that this function falls in the time complexity class of O( N^2 ).

It should be noted that adding in additional counters into your code is generally for testing and analysis purposes and should be removed, commented out, or otherwise isolated from final executables provided to users.

Empirical measurement of time

Example using psuedocode to be written