2D Haar Transform Computational Complexity I want to learn the computational complexity of the 2D Discrete Haar (Wavelet) Transform (DHWT). The number of operations (divisions, summations etc.) is the main focus. I think there are many different ideas on that. There are even papers claiming that we do not need any multiplications for it. I am confused. Any help? Thanks.

Edit: I should have added the orthogonality requirement for the Haar transform.
This is just to address the lack of multiplications:  why would there be?



The coefficients of the Haar wavelet (in 1D or 2D) are always +1 or -1.  There is no point in doing a multiplication to find the value or its negative.

Check out these notes, particularly this page: