Computing the weighted h-index
A common algorithm problem is that given a sequence of numbers, find a h-index. Where h-index is the largest integer such there are at least integers in the sequence is at least as large as .
Formally, we have the following problem.
Given , find the largest , such that .
If we the numbers are sorted, then a trivial time algorithm exists. If it is not sorted, then note that we can solve the problem on . In this case, the input numbers is at most , therefore can be sorted in time. Hence the total running time is .
Consider a weighted version of the problem where the above algorithm does not work.
Given a sequence of pairs of non-negative positive reals . Find the largest , such that .
An time algorithm still exists. For simplicity, we assume all ’s are distinct, so the input is a set. The case where ’s are not distinct is left as an exercise to the reader.
Define . We want to find the largest such that . First, we can find the median of , say . If , then we recurse on . Assume the optimum in the recursed solution is , we return as the solution. If , then we recurse and output the solution with input . The running time satisfies , which is .