Before revision:  In general, the time complexity for dealing with outliers in high dimensional space could be very large.
After revision:  They are in fact extremely challenging combinatorial optimization problems, since we cannot impose any restriction on the outliers. Therefore, their computational complexities are quite high especially when we consider the instances in high dimensional space could be very large.