9
$\begingroup$

Suppose we have a list $L$ consisting of $N$ numbers (may include repetitions).

I am curious which is more computationally intensive to calculate, the mean or the median?

Naively, I would suppose calculating the mean involves summing up the $N$ numbers and then dividing by $N$, hence it has linear $O(N)$ complexity.

Computing the median would need to perform some sort of sorting algorithm, https://en.wikipedia.org/wiki/Sorting_algorithm, it seems the best algorithm performs at $O(n\log n)$ complexity.

Hence, for general $N$, it is more computationally intensive to calculate median? Is my reasoning correct?

Thanks for any help.

Improve this question
$\endgroup$
3
  • $\begingroup$ en.wikipedia.org/wiki/Quickselect $\endgroup$
    – Pseudonym ♦
    Commented Jul 22, 2019 at 5:21
  • $\begingroup$ Note that computing the mean of a large number of floating point numbers needs more than $O(N)$, typically $O(N\ log\ N)$. $\endgroup$
    – Simon Richter
    Commented Jul 22, 2019 at 13:22
  • $\begingroup$ Do you want worst case performance or average (over the set of initial permutations of $L$) performance? For instance, quickselect is $O(N)$ on average, but $O(N^2)$ in the worst case. $\endgroup$
    – Eric Towers
    Commented Jul 22, 2019 at 17:45

2 Answers 2

Reset to default
10
$\begingroup$

You can find the median in linear time using the linear time selection algorithm. There are also faster randomized algorithms such as quickselect and Floyd–Rivest.

The two tasks are really incomparable, since computing the mean requires arithmetic (mainly addition) whereas computing the median requires comparisons.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ The median of medians is not generally the same as the median. It is sufficiently close for use in algorithms like quicksort to guarantee an O(n log n) time complexity, but it can deviate quite a bit from the actual media. $\endgroup$
    – Dreamer
    Commented Jul 22, 2019 at 13:57
  • $\begingroup$ Right, the problem is that Wikipedia doesn't have a page for the linear time selection algorithm based on median-of-medians. Let me assure you, however, that the exact median can be found in linear times. $\endgroup$
    – Yuval Filmus
    Commented Jul 22, 2019 at 14:54
  • $\begingroup$ @YuvalFilmus this might be what you're looking for. $\endgroup$
    – ryan
    Commented Jul 23, 2019 at 21:36
  • $\begingroup$ @ryan Right, that should be a separate article. Hopefully someone will make it so in the future. $\endgroup$
    – Yuval Filmus
    Commented Jul 23, 2019 at 22:10
2
$\begingroup$

Just quickly saying how can get find the median in linear time: Say you have a million items 0 .. 999,999 then the median is the average of items 499,999 and 500,000.

Run the quicksort algorithm. But after each partitioning, you don't sort both halves, you only sort the half (or two halves) containing elements #499,999 and 500,000.

The average would be O(n) if you just add all the values and divide by n. The problem is you get rounding errors. At the extreme, you could get a result that is less than the minimum or greater than the maximum of all values (especially if all items are equal to the same value x; due to rounding errors it's quite unlikely that your result is exactly x).

A reasonably precise method for large n is this: Add the numbers in pairs. Say $b_0 = a_0 + a_1$, $b_1 = a_2 + a_3$ etc. Then $c_0 = b_0 + b_1$, $c_1 = b_2 + b_3$ and so on, until only one number is left. Since the results are smaller than if you added sequentially, the errors are smaller. So you get a better approximation for the average.

That approximation is still not good. If the average you calculated is A, you then calculate the average of $a_i - A$. This is more precise since the values involved are smaller (the sum should in theory be 0 but isn't due to rounding errors), so you just add that average to A to get a better result.

It's still linear time, but it's a bit slower than just adding all the numbers.

Improve this answer
$\endgroup$

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.