Linear time algorithm for finding shifted max

Question

Assume that we are given an array $A[1..n]$ containing nonnegative integers (not necessarily distinct).

Let $B$ be $A$ sorted in the nonincreasing order. We want to compute $$m = \max_{i\in [n]} B[i]+i.$$

The obvious solution is sorting $A$ and then compute $m$. This gives an algorithm that runs in time $O(n \lg n)$ in the worst case.

Is it possible to do better? Can we compute $m$ in linear time?

---

My main question is the one above. But it would be interesting to know about the following generalization of the problem.

Let $B$ be $A$ sorted according to some comparison oracle $\leq$ and $f$ a function given by an oracle. Given $A$ and oracles for $\leq$ and $f$, what can we say about the time needed to compute $m = \max_{i \in [n]} f(B[i],i)$?

We can still compute $m$ in $O(n \lg n)$ time. But can we prove a super-linear lower-bound for this generalized case?

If the answer is yes does the lower-bound hold if we assume that $\leq$ is the usual order on integers and $f$ is a "nice" function (monotone, polynomial, linear, etc.)?

Answer 1

We can compute $m$ in linear time.

For simplicity suppose that the arrays are 0 based: $A[0..n-1]$, $B[0..n-1]$. We want to compute $m = \max_i B[i]+i$.

Let $max = \max_i A[i]$. Obviously $max \leq m$.

Let $A[j]$ be $B[k]$ after sorting. If $A[j] \leq max - n$ we have $$B[k] + k \leq B[k] + (n-1) = A[j] + (n-1) \leq (max-n) + (n-1) = max-1 < max \leq m.$$

Therefore we can ignore $A[j]$ when $A[j] \leq max - n$. We only need to consider the numbers in the range $[max-n, max]$.

We can use counting sort to sort the numbers in $A$ which are in the range $[max-n, max]$ in linear time and use the sorted list to compute $m$.

Answer 2

If the array $A$ consists of distinct integers, then $m = \max(A) + 1$, since the distance between adjacent entries in $B$ is at least $1$; the situation is more interesting when they need not be distinct.

For your more general question, imagine a situation in which $f(B[i],j)$ is only "interesting" when $i = j$. It seems possible to construct an adversary argument which forces you to query $f(B[i],i)$ for all $i$ before you can know $\max_i f(B[i],i)$, hence you need to sort $A$ in order to find the answer, which takes $\Omega(n\log n)$ comparisons. (There are some complications since it might be the case that we can test whether $A[i] = B[j]$ in constant rather than linear time by querying $f(A[i],j)$.) This is the case even if $f$ is a (high-degree) polynomial.