If we need to find vector in R^n which is orthogonal to given (n-1) vectors, this is basically solving linear system of equations and can be done in O(n^3) operation.

I wonder is there some simplification to do it if it is additionally known that vectors are v_i are orthonormal ?

Probably NO. But may be I am missing something ?

In my situation n=4 or n=8.

But even in R^3 I cannot guess the way I do not see how orthonormality of v_1 v_2 can help to find v_3.

====== Some clarifications, answering comments.

1) Of course, we can write "vector product" like formula i.e. just all (n-1)*(n-1) minors of our n*(n-1) matrix.
How will you calculate this minors ? The easiest way to calculate determinat is via Gauss decomposition i.e. O(n^3).

So it better directly apply Gauss decomposition to initial matrix and solve the problem in O(n^3) operations.

This is straightforward solution which I know. This does NOT use any my additional information that vectors are orthogonal.

2) We can choose some vector w and orthogonlize it. Complexity is n^2. Seems, solution ? No, because: there is no guarantee that we did not get ZERO. So we need to take w1 ... wn - linear independent - and orthogonalize each of them - then we have guarantee that you one of them is non-zero. But in this way we again have O(n^3) complexity.

notgeneralizing seamlessly to higher dimensions... – Federico Poloni Oct 27 '11 at 14:47