# Algorithm to find the median with a complexity of nlog(n)

Does it exist an algorithm to find a median of table with a complexity nlog(n) Thank

• Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? – Raphael Jun 6 '17 at 22:07
• The answer can be found ... everywhere. Plus, linearithmic time is almost trivial. Not sure what the question here is. – Raphael Jun 6 '17 at 22:08
• Define "complexity". Time? Space? Exact cost? $O$? $\Theta$? – Raphael Jun 6 '17 at 22:09

An algorithm I learned back in school was something along the following lines.

First, you will start out with one empty min-heap and one empty max-heap. You will then loop through your data, inserting the next piece of data into the max-heap. At each iteration of the loop, you check if the max-heap has 2 more pieces of data than the min-heap. If the max-heap does, you pop the max value in the max-heap and insert it into the min-heap.

After completing the insertion of the data stream, you then select the median value. If you have an odd number of data, you pop the max value off the max-heap as the median. If the data is even, you can pop the max/min value from the max/min heaps depending on what you decide is the median when data is an even size.

This approach is $O(n\log{n})$.

• Is that faster than Heapsort? – Raphael Jun 7 '17 at 4:51
• @Raphael Good question. Sadly I don't have an answer off the bat for that. I will give it some thought. My gut says Heapsort is faster, though. I feel like this algorithm just has the perk of being applicable to finding the median of streaming data as well. – spektr Jun 7 '17 at 5:10
• Hm, interesting thought. Since you can't throw away any of the values you can't really stream, though. Any form of "insertion" sorting (e.g. using BSTs) seems easier and not (much) slower. – Raphael Jun 7 '17 at 8:10
• @Raphael I don't seem to understand why not throwing away values means it cannot stream? As I see it, if we pretend we have unlimited storage, then this heap based approach updates the median estimate every time a new piece of data is added, regardless of if there's more data to be added or not afterward. I would think this means it can compute a streaming median? – spektr Jun 7 '17 at 14:02
• If that's what you mean by "streaming", then yes. Usually, one would suggest a $o(n)$ space bound, $n$ the input size (or, here, number of elements). – Raphael Jun 7 '17 at 21:36

If the table has $n$ elements then use k-th order statistic algorithm to find n/2-th element. It runs in O(n) in the worst case.

• Yes it's true. But the question is for a complexity of nlog(n). Thank you – SARR Jun 6 '17 at 22:01
• @smsarr An $O(n)$ algorithm is a fortiori an $O(n\log n)$ algorithm. – Yuval Filmus Jun 6 '17 at 22:08
• Welcome to Computer Science! Please consider not to encourage undesirable posting behaviour. – Raphael Jun 6 '17 at 22:08
• @smsarr, please read about big-O notation, little-O , and Lambda-notation, how and when they are used and how interpreted. You are asked to find O(nlog(n)) algorithm, we gave you one running in O(n) which is also O(nlog(n)) (as Yuval Filmus has already mentioned). What you are asking to find is one running in Lambda(nlog(n)). Your question is formulated wrongly. – fade2black Jun 6 '17 at 22:33
• @fade2black any chance you meant Landau notation instead of Lambda? – ryan Jun 7 '17 at 0:13

Yes there is.

Sort the array. A quicksort or mergesort will have nlog(n) time complexity. Afterwards, find the middle element in your array (you can calculate it by dividing array.length by 2) which is a O(1) operation.

The combination of sorting and finding the middle element will be nlog(n).

• You can do better because there is no need to sort the entire array, just the parts that contain the middle element. For instance, a randomized quicksort will do ok, and will give $O(n)$ on average. – Andrej Bauer Jun 6 '17 at 21:07
• Not to mention the celebrated linear time algorithm for finding the median, which uses $O(n)$ time in the worst case. – Yuval Filmus Jun 6 '17 at 21:31
• But the complexity asked is nlog(n) – SARR Jun 6 '17 at 21:32
• Please consider not to encourage undesirable posting behaviour. – Raphael Jun 6 '17 at 22:08