Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

New answers tagged

4 votes
Accepted

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

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 ...
user avatar
  • 1,257
1 vote

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

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 ...
user avatar
  • 3,437

Top 50 recent answers are included