Runtime comparison between the algorithms.

<p>(<b>a</b>) A comparison of power-set enumeration and the quadratic dynamic programming approach on small problems of the form from <a href="http://www.plosone.org/article/info:doi/10.1371/journal.pone.0091507#pone-0091507-g002" target="_blank">figure 2</a>. Note that axes are log-scaled, and so a widening gap between the curves indicates a super-linear speedup for the algorithm producing the lower curve. (<b>b</b>) A comparison of quadratic dynamic programming and the convolution tree approach on larger problems of this form. The convolution tree achieves a super-linear speedup and a super-linear reduction in memory consumption, making it applicable to much larger problems than either the quadratic dynamic programming approach or power-set enumeration. On very small problems (requiring substantially less than one second of runtime), the more sophisticated dynamic programming approaches have higher overhead, and are therefore slightly slower.