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