Big-O Scaling of R's cmdscale() I'm trying to run R's multidimensional scaling algorithm, cmdscale, on roughly 2,200 variables, i.e. a 2,200x2,200 distance matrix.  It's taking forever (about a day so far).  I don't know much about the algorithm used under the hood.  What's its big-O notation?  Is a more efficient, even if only approximate, algorithm available that's easy to set up and use?
 A: You should be able to test this on your system via Monte Carlo. For example:
try.cmdscale <- function(n) {
    x <- matrix(rnorm(n*n) ** 2,nrow=n,ncol=n);
    took.time <- system.time(cmdscale(x))
}

#repeat multiple times and take the median of the user.self + sys.self
#probably a better way to do timing?
multi.cmdscale <- function(n,ntrial = 11) {
    all.times <- replicate(ntrial,try.cmdscale(n))
    median(all.times[1,] + all.times[2,])
}

nvals <- c(8,16,32,64,128,256,512,1024)
tvals <- sapply(nvals,multi.cmdscale)
#ack! wish I could do a fit plot in logspace
plot(nvals,tvals,log="xy")

not so informative yet: If I could do some kind of fit on this plot, I could estimate the big O. (not so proficient in R yet, but learning).

A: Ironically, the MDS actually wasn't my problem.  The preprocessing I was doing was the issue.  I'm used to coding in lower-level languages and forgot how slow looping is in R.  I rewrote the preprocessing code using vector ops and the MDS actually only takes a few seconds.
