Operation Time-Squares: Theory vs Actual Time Complexity Exercise

A few days ago, a college student I tutor was asked to program a square-root function in C, using binary search, and assess its time complexity.

I was inspired by that exercise, and implemented 2 types of square-root functions. I then measured the run time and compared it to the theoretical time-complexity.

The two methods I used were binary search and geometry convergence.

Since I measured here run times for square-root functions, I nicknamed this one Operation Time-Squares.

Environment

I used my laptop, running Ubuntu Linux task under Windows 11, C code developed using VS, and compiled with 'gcc'. This Linux emulation has 1,000,000 ticks per second. Running and measuring was done while disconnected from the internet, and unnecessary apps were closed.

Binary Search

The idea behind this iterative method is to slice in half the search range in each step, until the searched range is smaller than the desired precision.

Geometry Convergence

In this iterative method, we treat the input as an area of a rectangle. In each iteration we 'guess' one side of the rectangle, and calculate the other side. If they are too far from one another, the next 'guess' will be the average of the 2 sides.

Theoretical Analysis (time complexity)

The 'precision' is the number of decimal digits we need the result to be accurate for, so a precision of 3 means a result that is at least 0.001 accurate (or 1e-3), and so on.

So, if we start with a number (let's say 2e6 = 2 million), and half the range until it reaches the desired precision (let's say 1e-4), then we'll need to narrow our range by 6 + 4 = 10 positions for the desired accuracy. In other words, the number of iterations is directly related to (order of...) log(input number/accuracy) or log(input number) + precision.

This calculation is common to both implementations (binary search and geometry convergence), as they both use halving guesses from the previous iteration.

The next question I asked myself was can this theory be validated using standard computing equipment?

Run design

• I used 'long double' as the major variable type for the calculation.
• I chose Input number range from 2 to 2e10, increasing by a constant factor of 10 (to enable easy analysis using log scale on charts).
• I chose precision to range from 3 to 10 decimal digits.
• to counter the overhead effects of calling timer functions calculation and printing I called the timer function, calculated the time, and printed the result once. However, the actual square root calculation was repeated 100,000 times. reported time is in ms (1e-3 sec).
• In order to further assess the overhead effect, an empty loop with just the overhead was coded and measured as well.

start = clock();
for (j=0; j<nRepeats[i]; j++){
     ; //empty loop, no-operation
}
end = clock();
cpu_time_used = ((long double) (end - start)) / (CLOCKS_PER_SEC/1000.0);        

• A similar loop was designed with sqrtl() of <math.h> instead of the no-op line, to be evaluated and compared to the user functions.
• The above setting was repeated 10 times for each setting combination, just to have significant statistics, and to avoid single runs' outliers.

for (;iCycles>0; iCycles--){                                    // 10 repeats for the whole process
      for (iDig=0; iDig<sizeArr(preDigs); iDig++){
          precision = preDigs[iDig];                          // 3 .. 10
          for (iSq=0; iSq<sizeArr(squares); iSq++){
              din = squares[iSq];                                 // 2, 20, 200, .. 2e10
              for(i=0;i < 100000 ; i++){                       // 100,000 repeats        

• While running, I disconnected the internet on my laptop, and closed unnecessary tasks, to avoid side effects on the run results.

Results Analysis

User functions vs. input number

The input number ranged from 2 to 2e10, factored by 10, as seen in the figure below. I looped through each setting for all desired precisions, repeated that 10 times, grouped and averaged the results for each tested input number.

As we can see from the results, the horizontal axis is a log-scale, and the linear trend line is very stable, with correlation > 99% for both tested functions, with similar slopes. This aligns perfectly with the theoretical analysis.

The reason for the Geometry Conversion being slightly better is because it requires less iterations for any given number in the first place, but the growth in run time is at a similar pace.

User functions vs. precision

Analyzing the above runs vs the desired variable precision (decimal digits), I grouped and averaged the run times according to the desired precision.

Here we can see that results are very reliable with correlations above 95%. The linear trend lines show that these functions are linear by the number of precision digits, which aligns with the theoretical analysis!

Comparing to native C's sqrtl() function from <math.h>

One last question I asked was how are first-year's student level functions compared to native C's sqrt() or sqrtl() functions?

In all the nested loops that I used for the user functions, I also embedded a 100,00 repetition loop that runs only sqrtl() function, and compared its run time to a 100,000 empty loop. The results are below.

As seen above, the run time both for the no-operations loop, as well as for the native sqrtl() function almost doesn't change.

The sqrtl() run-times averages at less than 0.6ms for 100,000 iterations (or 6 nanoseconds per calculation). If we subtract the overhead time of the no-operations loop, we get that sqrtl() net runtime is about 0.45ms for 100,000 iterations (or 45 nanoseconds per calculation).

Conclusions

1. Both Binary Search and Geometry Convergence user written functions run-times confirm their theoretical analysis as they evolve at an order or log(n) pace.
2. Measured run times for the above user written functions ranged from about 6ms to 40ms for 100,000 iterations, depending on its input number and desired precision. The Native C sqrtl() functions averaged at less than 0.6ms for the same effort.
3. While it was a great exercise in understanding time complexity and how to run a validation of it, one should prefer to use the native C sqrtl() function, as it is anywhere from 10 times to 90 times more efficient!