This invention provides a method and system for determining the number of bits to assign to a frequency range in a signal. The present invention is capable of bit allocation, with B total bits, among a plurality of N frequency ranges in time a time O(N log N), which is independent of the size of B. Embodiments of the present invention have many practical applications, including allocating bits among sub-channels in a multi-carrier communication system, and allocating bits among sub-bands in a signal representing digital multimedia, such as in JPEG or MPEG compressed files.