Comparison of Stahel-Donoho and Minimum Covariance Determinant estimation I am interested in detecting multivariate outliers in a low dimensional data set ($n>p$). Various high-breakdown robust methods for multivariate settings such as Stahel-Donoho and Minimum Covariance Determinant estimation is proposed in the literature. Can you give an advice and make a comparison than which estimator should be used and why? 
I have just found out that, due to computationally intensive calculation of Stahel-Donoho, the MCD estimation is preferable. How can I realize the intensity of calculation? Is there other reason for the superiority of MCD?
 A: Both algorithms have high quality implementations in a common environment so we can actually compare their running times. 
Check the CovSde and CovMcd functions in rrcov.
[Both algorithms have an argument nsamp which plays a similar role for both and impacts their computing times in a comparable way. Nevertheless, in the rrcov package the nsamp argument has different default values for the two algorithms, so in order for these comparisons to be fair, you'll need to make sure you are using the same values of nsamp when running both of them by setting it manually.]
To answer your question proper. Fixing the nsamp parameter to the same value, the running times of both algorithms now only depends on the size of the input matrix $\pmb X$. Denote $n$ ($p$) the numbers of rows (columns) of $\pmb X$.
The numerical complexity (and running times) of both algorithms scales roughly the same way as a function of $p$ (so the number of variables is not the culprit).
However, for large values of $n$, the running times of FastMCD scales less than linearly with $n$. This is due to the so called nested sub-sampling algorithm included in the FastMCD (section 3.3 of [0]) --CovSde has no comparable nested sub-sampling scheme.
The actual value at which the nested sub-sampling algorithm kicks in is set by the user but the default value is $n=600$. For large values of $n$, the nested sub-sampling algorithm can lead to substantial computational savings for FMCD.
You can see the effect of the nested sub-sampling algorithm by comparing the running times of both algorithms for $n<600$ (when neither uses nested sub-sampling):
library(rrcov)

n <- 600
p <- 8

nsamp <- 1000
x <- matrix(rnorm(n * p), nc = p)
system.time(CovMcd(x, nsamp = nsamp))
   user  system elapsed 
  0.116   0.000   0.114 
system.time(CovSde(x, nsamp = nsamp))
   user  system elapsed 
  0.084   0.000   0.082 

to their relative running times when $n>600$ and FastMCD's nested sub-sampling scheme kicks in:
n <- 6000
p <- 8

nsamp <- 1000
x <- matrix(rnorm(n * p), nc = p)
system.time(CovMcd(x, nsamp = nsamp))
   user  system elapsed 
  0.160   0.016   0.170 
system.time(CovSde(x, nsamp = nsamp))
   user  system elapsed 
  1.188   0.012   1.197 



*

*[0]: P. J. Rousseeuw and K. van Driessen (1999) A fast algorithm for the minimum covariance determinant estimator. Technometrics 41, 212--223.

