8.11. Efficiency Testing

We are going to try running some real procedures so we can understand their efficiency. To understand the efficiency of a procedure, we need to run it with different input sizes and time how long it takes for each of the inputs. Then, we look for a pattern in the results. All of the procedures will exhibit one of these three patterns:

The actual procedures we will test are in the program at the bottom of the page. There is a lot of code, you do not have to worry about most of it. What is important is that it defines procedureA, procedureB, procedureC, procedureD, and procedureE. Each procedure takes a number as its input. At the top of the program is the procedure doTest. To run a particular procedure, we just need to change line 6 to say something like procedureA(6) to run procedureA with an input of 6 - or procedureC(10) to run procedureC with an input of size 10.

When you run a procedure, it will make a drawing and print out how long the drawing took to make.

For example… The code below is already set up to run procedureA with an input size of 4 -procedureA(4) on line 6. I ran it and got a time of ~0.97 seconds. Then, to test the same procedure with an input of size 6, I change line 6 to procedureA(6). I run that and get a time of ~1.63 seconds. I do the same for input sizes of 8 and 10 (changing line 6 and then running the program again.) Here is what I get:











Looking at that pattern, I can see that each time I increase the Input size by 2, procedureA takes approximately ~0.6 more seconds. That steady growth means procedureA is Linear or O(n).

You have attempted of activities on this page