with (as contrasted with the FFT, which recursively splits both the upper branch and the lower branch). This leads to the following recurrence relation which leads to an O(N) time for the entire operation, as can be shown by a geometric series expansion of the above relation. As an example, the discrete Haar wavelet transform is linear, since in that case and are constant length 2. The locality of wavelets, coupled with the O(N) complexity, guarantees that the transform can be computed online (on a streaming basis). This property is in sharp contrast to FFT, which requires access to the entire signal at once. It also applies to the multi-scale transform and also to the multi-dimensional transforms (e.g., 2-D DWT). Other transforms The Adam7 algorithm, used for interlacing in the Portable Network Graphics (PNG) format, is a multiscale model of the data which is similar to a DWT with Haar wavelets. Unlike the DWT, it has a specific scale – it starts from an 8×8 block, and it downsamples the image, rather than decimating (low-pass filtering, then downsampling). It thus offers worse frequency behavior, showing artifacts (pixelation) at the early stages, in return for simpler implementation. The multiplicative (or geometric) discrete wavelet transform is a variant that applies to an observation model involving interactions of a positive regular function and a multiplicative independent positive noise , with . Denote , a wavelet transform. Since , then the standard (additive) discrete wavelet transform is such that where detail coefficients cannot be considered as sparse in general, due to the contribution of in the latter expression. In the multiplicative framework, the wavelet transform is such that This 'embedding' of wavelets in a multiplicative algebra involves generalized multiplicative approximations and detail operators: For instance, in the case of the Haar wavelets, then up to the normalization coefficient , the standard approximations (arithmetic mean) and details (arithmetic differences) become respectively geometric mean approximations and geometric differences (details) when using . Code example In its simplest form, the DWT is remarkably easy to compute. The Haar wavelet in Java: public static int[] discreteHaarWaveletTransform(int[] input) { // This function assumes that input.length=2^n, n>1 int[] output = new int[input.length]; for (int length = input.length / 2; ; length = length / 2) { // length is the current length of the working area of the output array. // length starts at half of the array size and