A method and device for reducing the computational complexity of a processing algorithm, of a discrete signal, in particular of the spectral estimation and analysis of bio-signals, with minimum or no quality loss, which comprises steps of (a) choosing a domain, such that transforming the signal to the chosen domain results to an approximately sparse representation, wherein at least part of the output data vector has zero or low magnitude elements; (b) converting the original signal in the domain chosen in step (a) through a mathematical transform consisting of arithmetic operations resulting in a vector of output data; (c) reformulating the processing algorithm of the original signal in the original domain into a modified algorithm consisting of equivalent arithmetic operations in the domain chosen in step (a) to yield the expected result with the expected quality quantified in terms of a suitable application metric; (d) combining the mathematical transform of step (b) and the equivalent mathematical operations introduced in step (c) for obtaining the expected result within the original domain with the expected quality; (e) selecting a threshold value based on the difference in the mean magnitude value of the elements of the output data vector of the transform said in step (b) and the preferred complexity reduction and degree of output quality loss that can be tolerated in the expected result within the target application; (f) pruning a number of elements the magnitude of which is less than the threshold value selected in step (e); and/or eliminating arithmetic operations associated with the pruned elements of step (f) either in the mathematical transform of step (b) and/or in the equivalent algorithm of step (c).