samples into j partitions. We compute M ( i + 1 ,j ) from M ( a,j − 1) ,a ≤ i using: where t$_{[}$$_{a}$$_{+0}$$_{.}$$_{5}$$_{,i}$$_{+1+0}$$_{.}$$_{5]}$ is the score of the cell from a + 0 . 5 to i + 1 + 0 . 5. This calculation takes O ( N ), and since we have O ( N $^{2}$) such items to calculate, this step takes O ( N $^{3}$). Since M$_{m}$ = M ( N,m ), the overall complexity for computing the scores for all m s is O ( N $^{3}$). Note that this algorithm enables us to calculate max$_{m}$$_{∈{}$$_{2}$$_{,...,m}$$_{max}$$_{}}$ { M$_{m}$ + log[ π ( I| m ) π ( m )] } in O ( N $^{3}$) for any function π ( m ), thus the regularized test statistic in Section 2.1 can also be computed in O ( N $^{3}$). Algorithm for the independence problem The algorithm is the same as de- scribed in Remark 3.1 for the ADP statistic for m = 2 and for the DDP statistic for m = 3 and m = 4, with the difference that the aggregation is by maximization (not summation) over the scores per partition. We are not aware of a polynomial-time algorithm for arbitrary m . We discuss ways to reduce the computational complexity in Section 6. Remark 3.2. We show in Appendix F that for univariate data the test of Heller et al. (2013) with an arbitrary distance metric, with or without ties, can be computed in O ( N $^{2}$) in a similar fashion, thus improving their algorithm by a factor of log N when X and Y are univariate. In simulations, we compared the power of our different test statistics in a wide range of scenarios. All tests were performed at the 0.05 significance level. Look-up tables of the quantiles of the null distributions of the test statistics for a given N were 4 Simulations 26 M ( i + 1 ,j ) = max a ∈{ 2 ,...,i $_{}}${ M ( a,j − 1) + t$_{[}$$_{a}$$_{+0}$$_{.}$$_{5}$$_{,i}$$_{+1+0}$$_{.}$$_{5]}$ } ,