What is the time complexity of the "norm" function in matlab?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
If you consider the $\ell^2$ norm of a real vector of size $n\times 1$, it requires $n$ operations to square all the elements, $n-1$ sums and $1$ square root so all in all the complexity is something like $O(3n)$. You can also test this empirically in Matlab with the commands tic & toc and with multiple vector sizes.
With norm 1 and inf you should also have a linear time complexity using the same reasoning.