Computational complexity of Gram-Schmidt orthogonalization algorithm

Question

What is the computational complexity of the Gram-Schmidt orthogonalization algorithm?

Suppose a matrix of m rows and k columns, how many operations are required to compute the orthogonalization?

If possible I would like to have the exact number of multiplications and additions.

EDIT: It seems to me that the total number of operations (multiplication + additions) is 3/2k^2m + 3/2mk +k^2/2 +k/2.
I would like to know if this is correct and if there is a quicker version.

Answer 1

Dot product takes m-1 additions and m multiplies.

Vector normalization takes 1 vector square (dot product), 1 square root and m divisions i.e.

m-1 +, m *, m /, 1 √

Subtraction of a vector projection takes 1 dot product, m multiplies and m additions, i.e.

2m-1 +, 2m *

Computation of the j-th vector takes (j-1) subtractions of projections, followed by a normalization, i.e.

(2m-1)(j-1)+m-1 +, 2m(j-1)+m *, m /, 1 √

You compute vectors from j=1 to k, so the factors (j-1) become the triangular number (k-1)k/2 and the terms independent of j are multiplied by k:

(2m-1)(k-1)k/2+(m-1)k +, 2m(k-1)k/2+mk *, mk /, k √

In the dot product, the m divisions can be traded for m multiplies by the inverse, yielding

(2m-1)(k-1)k/2+(m-1)k +, 2m(k-1)k/2+2mk *, k /, k √

So essentially 2mk² operations.