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.