With priming, the regression line correlating number of samples and standard deviation is roughly (sd^2)/6.5 + 1, which amounts to O(N^2) complexity. However, although this may seem slow, our method permits perfect recovery of complicated (albeit sparse) signals *with *arbitrary levels of AWGN. Thus, for reasonable data set sizes and values of standard deviation, the algorithm functions quite nicely for accurate signal reconstruction. Although if given infinite samples and time, it can recover any signal that is relatively sparse given infinite time.

Without priming the noise, and taking 50 samples, we can achieve O(1) complexity – extremely desirable, but the recovery percentage falls off rapidly with increase in noise standard deviation starting at standard deviation values around 3.5. Thus, this version of the algorithm could be desirable in non-critical applications where the strength of the noise is known to be low relative to that of the signal. We certainly would not recommend using the non-primed algorithm in data sensitive digital applications.