-an image whose SPAM features are close to the original one.
-The algorithm is thus computing a distance between each computed feature,
-andthe original ones
-which is at least in $O(343)$ and an overall distance between these
-metrics which is in $O(686)$. Computing the distance is thus in
-$O(2\times 343^2)$ and this modification
-is thus in $O(2\times 343^2 \times n^2)$.
-Ranking these results may be achieved with a insertion sort which is in
-$2.n^2 \ln(n)$.
-The overall complexity of the pixel selection is thus
-$O(n^2 +2.343^2 + 2\times 343^2 \times n^2 + 2.n^2 \ln(n))$, \textit{i.e}
-$O(2.n^2(343^2 + \ln(n)))$.
-
-Our edge selection is based on a Canny Filter,
-whose complexity is in $O(2n^2.\ln(n))$ thanks to the convolution step
-which can be implemented with FFT.
-To summarize, for the embedding map construction, the complexity of Hugo is
-at least $343^2/\ln{n}$ times higher than
-our scheme. For instance, for a squared image with 4M pixel per slide,
-this part of our algorithm is more than 14100 faster than Hugo.
-
-We are then left to express the complexity of the STC algorithm .
+an image whose SPAM features are close to the original ones.
+The algorithm thus computes a distance between each feature
+and the original ones,
+which is at least in $\theta(343)$, and an overall distance between these
+metrics, which is in $\theta(686)$. Computing the distance is thus in
+$\theta(2\times 343^2)$ and this modification
+is thus in $\theta(2\times 343^2 \times n^2)$.
+Ranking these results may be achieved with a quick sort, which is in
+$\theta(2 \times n^2 \ln(n))$ for data of size $n^2$.
+The overall complexity of the pixel selection is finally
+$\theta(n^2 +2 \times 343^2 + 2\times 343^2 \times n^2 + 2 \times n^2 \ln(n))$, \textit{i.e},
+$\theta(2 \times n^2(343^2 + \ln(n)))$.
+
+
+
+
+Let us focus now on WOW.
+This scheme starts to compute the residual
+of the cover as a convolution product which is in $\theta(n^2\ln(n^2))$.
+The embedding suitability $\eta_{ij}$ is then computed for each pixel
+$1 \le i,j \le n$ thanks to a convolution product again.
+We thus have a complexity of $\theta(n^2 \times n^2\ln(n^2))$.
+Moreover the suitability is computed for each wavelet level
+detail (HH, HL, LL).
+This distortion computation step is thus in $\theta(6n^4\ln(n))$.
+Finally a norm of these three values is computed for each pixel
+which adds to this complexity the complexity of $\theta(n^2)$.
+To summarize, the complixity is in $\theta(6n^4\ln(n) +n^2)$
+
+What follows details the complexity of the distortion evaluation of the
+UNIWARD scheme. This one is based to a convolution product $W$ of two elements
+of size $n$ and is again in $\theta(n^2 \times n^2\ln(n^2))$,
+ and a sum $D$ of
+these $W$ which is in $\theta(n^2)$.
+This distortion computation step is thus in $\theta(6n^4\ln(n) + n^2)$.
+
+
+Our edge selection is based on a Canny filter. When applied on a
+$n \times n$ square image, the noise reduction step is in $\theta(5^3 n^2)$.
+Next, let $T$ be the size of the Canny mask.
+Computing gradients is in $\theta(4Tn^2)$ since derivatives of each direction (vertical or horizontal)
+are in $\theta(2Tn^2)$.
+Finally, thresholding with hysteresis is in $\theta(n^2)$.
+The overall complexity is thus in $\theta((5^3+4T+1)n^2)$.
+
+
+
+
+
+We are then left to express the complexity of the STC algorithm.
