Time and Space Complexity Graphs¶
In [1]:
%pylab inline
Populating the interactive namespace from numpy and matplotlib
Let's just copy & paste the table from http://fredrikj.net/blog/2014/03/new-partition-function-record/
In [2]:
%%file timings.txt
108 11132 3328 2.8 0.037 0.07 0.031 0.032 0.004 0.016
109 35219 9721 3.05 0.237 0.29 0.061 0.227 0.008 0.035
1010 111391 28601 4.89 0.441 0.75 0.307 0.429 0.039 0.184
1011 352269 84632 9.82 1.834 3.29 1.449 1.805 0.168 0.841
1012 1113996 251600 19.82 6.247 10.39 6.169 4.159 1.004 3.475
1013 3522791 750925 61.31 25.637 43.06 25.436 17.435 3.282 15.834
1014 11140072 2248842 202.81 104.07 188.33 103.57 84.346 12.389 66.326
1015 35228031 6754864 553.77 441.603 845.42 404.175 440.417 47.035 263.662
1016 111400846 20343453 1469.73 1614.84 2858.31 1611.65 1244.68 194.188 1099.58
1017 352280442 61413562 4593.42 7398.2 13643.7 6251.35 7389.06 762.067 4167.94
1018 1114008610 185795691 12937.41 23354.6 44330.3 23327.1 20997 2913.12 16171.8
1019 3522804578 563188404 38881.84 87825.3 170934 87742.6 83184.9 10860.9 61796.3
1020 11140086260 1710193158 131071 399206 738425 339610 398959 42394.2 239099
Overwriting timings.txt
In [3]:
D = loadtxt("timings.txt")
In [4]:
n = array([10**i for i in range(8, 21)], dtype=float)
In [5]:
mem = D[:, 3]
wall = D[:, 4]
For time complexity, it looks like it is Θ(n0.5+ϵ) with ϵ=0.1:
In [6]:
eps = 0.1
fit = n**(0.5+eps)
fit = fit * wall[-1] / fit[-1]
In [7]:
loglog(n, wall, "x-", label="data")
loglog(n, fit, "-", label="$\mathrm{const}\cdot n^{0.5+\epsilon}$ with $\epsilon=%.3f$" % eps)
legend(loc="best")
grid()
xlabel("$n$")
ylabel("Wall [s]")
title("Time complexity");
For space complexity, it looks like it is Θ(n0.5+ϵ) with ϵ=−0.02:
In [8]:
eps = -0.02
fit = n**(0.5+eps)
fit = fit * mem[-1] / fit[-1]
In [9]:
loglog(n, mem, "x-", label="data")
loglog(n, fit, "-", label="$\mathrm{const}\cdot n^{0.5+\epsilon}$ with $\epsilon=%.3f$" % eps)
legend(loc="best")
grid()
xlabel("$n$")
ylabel("Mem [MB]")
title("Space complexity");
