Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 5 down vote favorite

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.

share|improve this question
I presume, you have seem this: en.wikipedia.org/wiki/Selection_algorithm ? – Dirk Feb 10 '12 at 11:37
yes, but i doesn't discuss the constants in front of the complexities.... – user189035 Feb 15 '12 at 11:12

1 Answer

up vote -1 down vote

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.

share|improve this answer
To compute the median one must make a sorted list, except, errh, you know, this ain't so – user189035 Mar 25 at 16:13
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. – EngrStudent Mar 25 at 16:45
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. – user189035 Mar 25 at 17:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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