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$
2

1 Answer 1

-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$
3
  • $\begingroup$ To compute the median one must make a sorted list, except, errh, you know, this ain't so $\endgroup$
    – user189035
    Mar 25, 2013 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$ Mar 25, 2013 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, 2013 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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