Return to Answer

First compute a Cholesky factorization of the covariance matrix. Now your tentative new covariance matrix is a rank-2 update of the old, $$ M_{new}=M_{old}+\frac{1}{n}x_{new}x_{new}^T-\frac{1}{n}x_{old}x_{old}^T. $$ You can use Sylvester's formula here to compute the determinant of the update; for this you'll only need to solve a linear system, which is $O(n^2)$ using your Cholesky factorization.

Then when your "replacement" take place for real you just have to update the Cholesky factorization, and there are algorithms to do that (low-rank updates of Cholesky factorization) in $O(n^2)$ as well. Check Matlab's cholupdate for instance.

So you pay $O(n^3)$ at the first step and then $O(n^2)$ per step.

EDIT: better and clearer algorithm

First compute a Cholesky factorization of the covariance matrix. Now your tentative new covariance matrix is a rank-2 update of the old, $$ M_\text{new}=M_\text{old}+\frac{1}{n} x_\text{new} x_\text{new}^T-\frac{1}{n} x_\text{old} x_\text{old}^T. $$ You can use Sylvester's formula here to compute the determinant of the update; for this you'll only need to solve a linear system, which is $O(n^2)$ using your Cholesky factorization.

Then when your "replacement" take place for real you just have to update the Cholesky factorization, and there are algorithms to do that (low-rank updates of Cholesky factorization) in $O(n^2)$ as well. Check Matlab's cholupdate for instance.

So you pay $O(n^3)$ at the first step and then $O(n^2)$ per step.

EDIT: better and clearer algorithm

First compute a Cholesky factorization of the covariance matrix. Now your tentative new covariance matrix is a rank-2 update of the old, $$ M_{new}=M_{old}+\frac{1}{n}x_{new}x_{new}^T-\frac{1}{n}x_{old}x_{old}^T. $$ You can use Sylvester's formula here to compute the determinant of the update; for this you'll only need to solve a linear system, which is $O(n^2)$ using your Cholesky factorization.

Then when your "replacement" take place for real you just have to update the Cholesky factorization, and there are algorithms to do that (low-rank updates of Cholesky factorization) in $O(n^2)$ as well. Check Matlab's cholupdate for instance.

So you pay $O(n^3)$ at the first step and then $O(n^2)$ per step.

EDIT: better and clearer algorithm

First compute a Cholesky factorization of the covariance matrix. Now your tentative new covariance matrix is a rank-2 update of the old, $$ M_{new}=M_{old}+\frac{1}{n}x_{new}x_{new}^T-\frac{1}{n}x_{old}x_{old}^T. $$ You can use Sylvester's formula here to compute the determinant of the update; for this you'll only need to solve a linear system, which is $O(n^2)$ using your Cholesky factorization.

Then when your "replacement" take place for real you just have to update the Cholesky factorization, and there are algorithms to do that (low-rank updates of Cholesky factorization) in $O(n^2)$ as well. Check Matlab's cholupdate for instance.

So you pay $O(n^3)$ at the first step and then $O(n^2)$ per step.

EDIT: better and clearer algorithm

You can compute a $LDL^T$ factorization of your covariance matrix, i.e., a factorization in which $L$ is lower triangular with ones on the diagonal and $D$ is diagonal. Then you can interpret every possible "replacement" as a rank-2 update to $D$, so it is simple to compute its determinant. The dominant cost would be solving a linear system with $L$, which costs $O(n^2)$.

Then when your "replacement" take place for real you have to update the LDL^T factorization, and there are algorithms to do that in $O(n^2)$ as well.

I am looking now at the manual page for Matlab; they do not have algorithms for updating LDL but only for Cholesky, but it is essentially the same thing up to diagonal scaling.

First compute a Cholesky factorization of the covariance matrix. Now your tentative new covariance matrix is a rank-2 update of the old, $$ M_{new}=M_{old}+\frac{1}{n}x_{new}x_{new}^T-\frac{1}{n}x_{old}x_{old}^T. $$ You can use Sylvester's formula here to compute the determinant of the update; for this you'll only need to solve a linear system, which is $O(n^2)$ using your Cholesky factorization.

Then when your "replacement" take place for real you just have to update the Cholesky factorization, and there are algorithms to do that (low-rank updates of Cholesky factorization) in $O(n^2)$ as well. Check Matlab's cholupdate for instance.

So you pay $O(n^3)$ at the first step and then $O(n^2)$ per step.

EDIT: better and clearer algorithm