Question

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.

Answer 1

You want to find the last row of an orthogonal matrix given $n-1$ rows, right? Since the sum of squares in each column is $1$, you can find the absolute values of the entries in about $n^2$ operations. So, it remains to determine the sign pattern for non-zero entries. That can be also done quickly: add two columns with non-zero last entries. The sum should have norm 2 and this is enough to determine if the signs of the last entries were the same or different because $(a+b)^2\ne(a-b)^2$. Of course, this works only if the $n-1$ orthonormal vectors are known with reasonable precision but it requires no random choice.

Edit: All right. Here goes the formal algorithm as I would try it in a real implementation:

Let $v_i=(v_{ij})$ be the given vectors ($i=1,\dots,n-1$, $j=1,\dots,n$).

Put $v_{nj}=\sqrt{1-\sum_{i=1}^{n-1}v_{ij}^2}$ (return $0$ if the expression under the root is slightly negative and write an error message if it is noticeably negative).

Choose $J$ such that $v_{nJ}=\max_j v_{nj}$.

For $j\ne J$ compute $S=\sum_{i=1}^{n-1} v_{ij}v_{iJ}$. If $S\le 0$, leave $v_{nj}$ as is, otherwise change its sign to $-$. After that is done, for control, compute $T=v_{nj}v_{nJ}$ and check that $S+T=0$ with decent precision. If not, write an error message.

Take two or three scalar products of thus obtained $v_n$ with previous vectors (say, $v_1$ and $v_{n/2}$) and check the norm of $v_n$. If those tests pass with decent precision, consider the task done.

I know, I'm sort of paranoid about possible errors in my programming but it you'd better detect the situation when you try this on a system of vectors that is not quite orthonormal :).