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.



Find vector in R^n which is orthogonal to given (n-1) vectors v_i under condition v_i are orthonormal.
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 :).


