This work explores the performance ofafamily of algorithms for computing the Walsh-Hadamard transform (WHT), ausefulcomputationin signal and image processing [1, 2, 5].The algorithms exhibit a wide range of performance and it is non-trivialtodetermine which algorithm is optimalon agiven computer[4].This paper providesatheoretical basis fortheperformanceanalysis.Performance is modelledby afamily of recurrence relations that determine the number of instructions required to executeagiven algorithm,and are related to standard divide and conquer recurrences[6, 3].However,since thereare a variablenumber of recursive parts which can grow to infinity as theinputsize increases, new techniquesare required for their analysis. In the full version of this paper,the minimum,maximum,expected values,and variances are calculated and the limiting distribution is obtained.