The Base 3 Counter algorithm's runtime is bound by 
. If we
assume the instructions in the for loop in calccost take
constant time then calccost
is bounded above by n the number of tasks, and
the number of times the loop executes times the constants, cn. The same
analysis shows that calccost is bound from below by cn, therefor
making calcost 
. In the large for loop from 0
to 
calccost is executed times, making the whole run time
bound by .
Below is a plot of the above data I collected on the running time of Base 3
Counter. These test were done on waldrog using the systems time
command and reading off the real output. Plotted with the data points is
the curve of 
with k set to 8.7E-6.
The curve of t matches with the data points which shows that
is correct. It is interesting to see that by changing the
machine Base 3 Counter runs on or compiling the program optimized only
changes k a small amount, this really shows how much the order
dominates the run time.