How to evaluate the Order of Growth

 

Let us assume we have a process that takes more time with a larger input (e.g. higher number of “rows”). Actually, here is a concrete example in the context of ABAP development.

I suggest to compute the order-of-growth and make sure your run-time is acceptable for large input. We cannot avoid some maths (power law, log) here, but in those times of Covid19, you should have seen nice looking animations explaining why exponential growth can be so bad.

If the order of growth is 2 (quadratic) or higher, you have a potential disaster at hand. You must then keep the input size small at all costs or find another solution.

Now if have have at least two different measurements of your run-time as a function of the input size, then you can already estimate an order-of-growth.

From the vantage of software, the running time T is described as a function T(N) of an input size N (e.g. number of “rows”). We model this dependency as power law

  • T(N) = c N^b

where c is a constant.

From this formula, the order-of-growth b can be easily estimated by comparing T(N) with T(2N) based on the doubling hypothesis, so b is equal to

  • log( T(2N) / T(N) ) / log( 2 ) .

I implemented this logic in an unit test, using the fact that b is also equal to

  • log( T(10 N) / T(N) ).
  METHOD profile.
    CLEAR rs_time.
    rs_time-size = iv_size.
    DATA(lv_start) = mi_timer->get_runtime( ).
    run_data( iv_size ).           " <---- The Code under Test
    rs_time-time = mi_timer->get_runtime( ) - lv_start.
    IF iv_time GT 0.
      rs_time-lg_ratio = log10( rs_time-time / iv_time ).
    ENDIF.
  ENDMETHOD.                    "profile

  METHOD performance.
*   empirical analysis
    CONSTANTS c_precision TYPE f VALUE '1e-2'.
    DATA lv_size TYPE syindex VALUE 1.
    mi_timer = cl_abap_runtime=>create_hr_timer( ).
    DATA(ls_time) = profile( iv_size = 0
                             iv_time = 0 ).
    DO 6 TIMES.
      ls_time = profile( iv_size = lv_size
                         iv_time = ls_time-time ).
      lv_size = lv_size * 10.
    ENDDO.
    IF ( ls_time-lg_ratio - c_precision )  > 1 .
      cl_abap_unit_assert=>fail( msg = | Performance: { ls_time-lg_ratio } | ).
    ENDIF.
  ENDMETHOD.

cf. Introduction to Programming in Java by R. Sedgewick, K. Wayne