I would like to know whether the constant in the time complexity of computing the median is different from that of computing general quantiles.
In R for example:
fx01<-function(ll,a) quantile(a[,ll],0.75) fx02<-function(ll,a) median(a[,ll]) n<-1000 d<-1000 a<-matrix(rnorm(n*d),n,d) system.time(lapply(1:d,fx01,a=a)) system.time(lapply(1:d,fx02,a=a))
Typically, I observe that computing a general quantile takes 2-4 times more time than a median. I would like to know if this is an implementation issue or whether it is set in stone.