Complexity Comparison of FHT and MFHT

As the dimensionality $k$ of parameter space increases, the MFHT becomes slower than the FHT. This is because the computational work at each hypercube subdivision increases faster for the MFHT as $k$ increases than for the FHT.

Most of the work in the subdivision procedures ($divide\_cube$ for the FHT and $divide\_rectangle$ for the MFHT) goes into two stages. Firstly, arrays are calculated that are to be passed on to children. For the FHT plane finder these are the eight ($2^k$ in general) ${\bf R}_{\bf b}$ normalised distance arrays, whereas for the MFHT line finder, ${\bf I}^{\rm av}$ is the only such array (there are $3^{k-1} - 2^{k-1}$ arrays in general). In both cases the calculation of an array element involves two calculations: an addition and multiplication by two in the FHT, an addition and a division by two in the MFHT. The second time consuming part is the voting, i.e. the test for intersection of hyperplane with hypersphere/hypercube. For the FHT plane finder this is just a single comparison for each of the eight child cubes ($2^k$ comparisons generally) whereas for the MFHT line finder, 9/2 comparisons (on average) and four boolean expressions are evaluated (for general $k$ these figures become $3^k/2$ and $2^k$ respectively). All these figures are summarised in table 5.1.

Table 5.1: Complexity comparison of FHT and MFHT. The figures are the number of calculations at each hypercube subdivision, for each hyperplane.

	FHT	MFHT
multiplications/divisions	$2^k$	$3^{k-1} - 2^{k-1}$
additions	$2^k$	$3^{k-1} - 2^{k-1}$
comparisons	$2^k$	$3^k/2$
boolean expressions	0	$2^k$

Since $3^k$ increases faster than $2^k$, the FHT will overtake the MFHT for speed as $k$ increases. In fact tests have shown the MFHT plane fitter to be about 25% slower than the FHT. The memory space advantage of the MFHT is also reduced, since $3^2 - 2^2 = 5$ new arrays are required at each subdivision as against eight for the FHT (which again could be altered so as to require only one array, at the cost of some loss of speed).