Time and Space Complexity Graphs

In [1]:
%pylab inline
Populating the interactive namespace from numpy and matplotlib
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 $\Theta(n^{0.5+\epsilon})$ with $\epsilon=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 $\Theta(n^{0.5+\epsilon})$ with $\epsilon=-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");