# Finding Median value given a tuple (value, frequency) in O(n) worst case time complexity

An accountant in a big firm would like to find the median of the salaries of all employees. The data they received is a list of size n containing the tuples $$\left\{s_{i\ },f_{i\ }\right\}_{i=1}^{n}$$, where the number $$s_i$$ is the salary and the integer $$f_i$$ is the number of employees that got salary $$s_i$$ in the firm.

Suggest an algorithm that gets the list as input and returns the median salary of the employees at the firm in time O(n) in the worst case, and justify why this is the running time of your algorithm. For example for the input (8000, 4),(20000, 1),(10000, 2) the output should be 8000 since the full, sorted list of salaries is: 8000, 8000, 8000, 8000, 10000, 10000, 20000. Remark: $$\sum_{ }^{ }f_{i\ }$$ (i.e. the number of employees) may be way bigger than n so you are not expected to write the expanded list of salaries.

Hi, I was given this question and was stuck on it for a while. It seems no matter what I try to do I will exceed the $$O(n)$$ worst time restriction.. The direction I was going with is to somehow try to unzip the tuples into a list and use a simple run of $$MedianOfMedians$$ algorithm to find the median, but as the question states, we can't just create a single list of all salaries as the size of the new list will exceed $$n$$. I feel like it has something to do with manipulation the values according to the total number of employees or maximum salary, etc, but no matter what kind of value manipulation I've tried it seems to fail.

I'm a bit lost as to how I am supposed to solve this, considering we've only learned very basic algorithms so far, such as selection and linear sorting algorithms in addition to some basic data strcuture such as trees, heaps, etc..

There is probably some trick involved which I am not getting, but what is it?

• What is $n_i$ ?
– user16034
May 7, 2022 at 9:39
• Sorry, it was a typo. I meant s_i May 7, 2022 at 10:15
• "we've [...] learned [...] linear sorting algorithms" - Which ones? May 7, 2022 at 14:47
• Please credit the original source of the problem. That is what you are supposed to do. If it is a course, identify the course or the textbook or the instructor. (Furthermore, without that I would not upvote.) May 7, 2022 at 23:59
• cs.stackexchange.com/help/referencing
– D.W.
May 8, 2022 at 4:01

I think you can still use the linear time selection algorithm (median of medians) here. Let's call this algorithm $$Select$$ and let the median position be $$m$$, which is initially equal to $$n/2$$.Recall that the algorithm has 3 phases:

1. Group by 5 and select median of each group
2. Choose partition element $$p$$, by applying $$Select$$ to find the median of the medians.
3. Partition the elements around $$p$$. If $$p$$ is the true median, return it otherwise recursively apply $$Select$$ to one side of the partition.

Observe first that it is possible that the frequency of each tuple is 1, which reduces the problem to the original median selection.

Below we describe $$Select'$$ a modification of $$Select$$ that allows values with frequencies greater than 1:

1. Group by 5 and select median of each group based only on the value, ignoring the frequency.
2. Choose $$p$$ by applying the $$Select$$ algorithm to find the median of the medians. Since the original $$Select$$ algorithm is being used, the frequencies of the medians are not considered in the selection.
3. Partition the tuples around $$p$$. During the partition, sum-up the frequency of each tuple that ends up on the left side of $$p$$. Call this sum $$l$$. If $$l \geq m$$, recursively apply $$Select'$$ to the left partition. Else, if ($$l + p.frequency) \geq m$$, then $$p$$ is the median and we are done. Otherwise, update $$m$$ to $$m - (l+p.frequency)$$ and recursively apply $$Select',$$ on the right partition.

The reason why we ignore the frequency on steps 1 and 2, is to guarantee that on step 3, the number of elements removed after partition is similar to what is expected from the original $$Select$$ algorithm. The additional step of accumulating the frequencies to get $$l$$, increases the running time of the partition step by a constant factor only, hence it has no significant effect on the asymptotic running-time of the algorithm. Therefore, the running-time of $$Select'$$ is also $$O(n)$$.

• @JohnL., thanks for the clarification. I made an update, hopefully this makes the answer clearer. May 7, 2022 at 23:43
• This algorithm can just use $Select$ to find the median of the values (the $s_i$'s). There is no need to repeat the description of $Select$ as step 1 and 2 inside the description of $Select'$ again. May 8, 2022 at 3:54
• Where is the analysis of time-complexity? May 8, 2022 at 4:00
• Sorry but I don't get what you mean when you say that the $Select$ can be used exactly as it is to find the median. I decided to include steps 1 and 2 in the modified version just to emphasize the importance of not considering the frequency in selecting the partition element, the reason for this is discussed in the last part of my answer. May 8, 2022 at 4:18
• The cost for summing the frequency will be added to the $cn$ term, which represents the cost of the partition. It would not affect the recursive terms, that is why it retains the original running-time of $Select$. Recall that in partition we scan the entire array to find elements that must be placed on ther correct partition with respect to $p$. Now during this scan, when we find an element less than $p$, we add its frequency to $l$. This step will increase the time of each scan by a constant additive factor only, hence constant factor increase overall to the entire partition procedure. May 8, 2022 at 6:51

If the pairs are given ordered by increasing salary, it suffices to compute the prefix sum of the frequencies $$F_k:=\sum_{i=1}^k f_k$$ and find the sum closest to the half of the total.

If the pairs are not ordered, you are stuck.

• Does that mean that is it impossible to solve the problem in O(n) worst case time without sorting the salaries first? May 7, 2022 at 12:38
• @MathCurious: I don't see a way.
– user16034
May 7, 2022 at 12:40