Algorithms 1 week 1 exercise 2

question1.py

"""
The theoretical order-of-growth is N ^ (29/12) = 2.42

The empirical order-of-growth is N ^ (log_2 ratio)

                                  log_2
        N   seconds     ratio     ratio
---------------------------------------
      256     0.000         -         -
      512     0.001         -         -
     1024     0.004      4.00      2.00
     2048     0.020      5.00      2.32
     4096     0.107      5.35      2.42
     8192     0.576      5.38      2.43
    16384     3.083      5.35      2.42
    32768    16.288      5.28      2.40
    65536    87.258      5.36      2.42
   131072   466.320      5.34      2.42
   262144  2485.866      5.33      2.41
   
   (seed = 432237)
"""

from math import ceil
from math import log


def norm(num):
    """Normalizes values to 2 digits."""
    return ceil(num * 100) / 100


def main():
    numbers = [0.000, 0.001, 0.004, 0.020, 0.107, 0.576, 3.083, 16.288, 87.258,
               466.320, 2485.866]
    # if first value is not 0 add one more value.
    # this value will be removed on calculations
    if numbers[0]:
        numbers = [0] + numbers
    # match values with previous value so we can get ratio of them
    tuples = zip(numbers[1:], numbers[2:])
    # print values
    for prev, num in tuples:
        ratio = norm(num/prev)
        ratio_log2 = norm(log(ratio, 2))
        print '%s  %s  %s' % (num, ratio, ratio_log2)
    # calculate average
    average = norm(sum(norm(log(norm(num / prev), 2))
                       for (prev, num) in tuples)/len(tuples))
    # pring average
    print 'average = %s' % average


if __name__ == '__main__':
    main()