# Time complexity of $l_2$-norm of a vector

What is the complexity (in flops, floating-point operations) of taking the $l_2$-norm of vector $\mathbf{v}\in\mathbb{R}^n$ (or $\mathbf{v}\in\mathbb{C}^n$ if a difference exists).

We have the following definition of the $l_2$-norm of $\mathbf{v}$:

$$\lVert\mathbf{v}\rVert_2= \sqrt{|v_1|^2+\dots+|v_n|^2}$$

where $|v_i|$ is the absolute value of $v_i$ (or complex modulus if $v_i$ complex).

I guess that what bothers me the most is the square-root computation. I found that the square-root is considered one flop, and hence the complexity is $2n$ flops.

Isn't that wrong since the square-root should take more time to compute?

• Side note: these days multiplication-addition pairs are fused into FMA's, so depending on what your goal is here, it might be $n+1$ flops for the whole formula. – Kirill Apr 23 '18 at 1:13
• I think many computer scientists reserve "complexity" to mean something a different than flop counting (though both are important). Complexity is about describing the asymptotic behavior of the time (or memory, etc) in terms of the size of an arbitrarily large input. Here, only the time for the summation is sensitive to n. Even if computing a square root is slower than an add/multiply (certainly is), the time to perform just one of them is insensitive to n and has no contribution to the "complexity" for large n (in the CS-theory sense of the word). – rchilton1980 Apr 23 '18 at 14:44
• @rchilton1980 relevant point. – Learn_and_Share Apr 23 '18 at 14:48

The above assumes that you are implementing the $\ell^2$ norm in the most straight-forward way without using fused-multiply additions, vectorized operations, etc.