5
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

To compute the median one must make a sorted list, count the number of elements in the list, and read either one or two values in the list depending on the number of elements.

http://mathworld.wolfram.com/StatisticalMedian.html

I see no reason why this would take substantially longer for any other quantile operation.

$\endgroup$
  • $\begingroup$ To compute the median one must make a sorted list, except, errh, you know, this ain't so $\endgroup$ – user189035 Mar 25 '13 at 16:13
  • $\begingroup$ There are a number of "ifs" in the median of medians method, particularly regarding pivot choices. I was going to suggest that if another method were being used and failed then the quantiles may be being computed using the previously described method. Is it intuitive that as you approach the tails the "good" pivots become more sparse, or harder to find? I wonder if there is a "radius of utility" for which quantiles could be found efficiently as a function of sample size. $\endgroup$ – EngrStudent - Reinstate Monica Mar 25 '13 at 16:45
  • $\begingroup$ I don't understand your comment. I have never seen a an open source library using the method you suggest for computing the quantiles. I would think that most use a variant of the partition method with random pivots. Obviously, complexity counts are for asymptotic values of n and when n is small other factors may dominate. But for the values of n in the ballpark of those hinted at in my question I doubt this will be the case. $\endgroup$ – user189035 Mar 25 '13 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.