Power spectrum estimators for large CMB datasets

Forthcoming high-resolution observations of the Cosmic Microwave Background (CMB) radiation will generate datasets many orders of magnitude larger than have been obtained to date. The size and complexity of such datasets presents a very serious challenge to analysing them with existing or anticipated computers. Here we present an investigation of the currently favored algorithm for obtaining the power spectrum from a sky-temperature map --- the quadratic estimator. We show that, whilst improving on direct evaluation of the likelihood function, current implementations still inherently scale as the equivalent of $O(N_{p}^{3})$ in the number of pixels or worse, and demonstrate the critical importance of choosing the right implementation for a particular dataset