<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-10-09T05:07:22.797Z
What if A has n - 1 zeros and a single one? Then the answer is n, not 1.
Grigory Yaroslavtsev
CC BY-SA 3.0
2013-10-09T05:48:54.697Z
Hi Yuval. There can be repeated numbers in $A$. As Grigory said the solution doesn't seem to work.
Kaveh
CC BY-SA 3.0
2013-10-09T05:53:30.717Z
I think I see your idea for the lower-bound argument: given $A$ we can compute $B$ quickly using the query pairs made to $f$ by an algorithm solving the problem in time $o(n\lg n)$. We can make sure the algorithm queries $f$ on all $(B[i],i)$ but we cannot make sure it doesn't query other pairs. However we can set $f$ for other pairs to be a distinguishable value so we can discard those pairs.
Kaveh
CC BY-SA 3.0
2013-10-09T04:41:37.587Z
2013-10-09T05:52:27.823Z
2013-10-09T05:52:27.823Z
Yuval Filmus
<p>We can compute $m$ in linear time.</p>

<p>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$.</p>

<p>Let $max = \max_i A[i]$. 
Obviously $max \leq m$.</p>

<p>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 &lt; max \leq m.$$</p>

<p>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]$.</p>

<p>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$.</p>

CC BY-SA 3.0
2013-10-09T10:14:04.147Z
... mmm ... but what is the cost of C[x]=C[x]+1 ?!?
Marzio De Biasi
CC BY-SA 3.0
2013-10-10T02:23:45.593Z
is there a problem with your answer? because it seems fine to me: you are saying we only care about array elements with values in $[M-n, M]$, so we can use counting sort. This works for the general problem whenever $|f(B[i], i) - B[i]| = O(n)$ for all $i$.
Sasho Nikolov
CC BY-SA 3.0
2013-10-10T04:47:12.900Z
Thanks @Marzio. :) I slightly edited your answer for clarity. Feel free to roll-back my edit or edit further.
Kaveh
CC BY-SA 3.0
2013-10-10T07:54:19.590Z
This solution seems to work also for any $f(x,i)$ where for all $x$ and $i\leq n$, $|f(x,i)-x| = O(n)$.
Kaveh
CC BY-SA 3.0
2013-10-10T14:07:35.357Z
@Kaveh: edit is ok! I wrote the answer quickly and I was not even sure of its correcteness :-S
Marzio De Biasi
CC BY-SA 3.0
2013-10-09T10:04:17.073Z
2013-10-10T06:00:04.387Z
2013-10-10T06:00:04.387Z
Marzio De Biasi
<p>Assume that we are given an array $A[1..n]$ containing nonnegative integers (not necessarily distinct).</p>

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

<p>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.</p>

<blockquote>
  <p>Is it possible to do better? Can we compute $m$ in linear time?</p>
</blockquote>

<hr>

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

<p>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)$?</p>

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

<p>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.)?</p>

<cc.complexity-theory><ds.algorithms><optimization><sorting>
Linear time algorithm for finding shifted max
Kaveh
# Linear time algorithm for finding shifted max

(Asked by: username_0 on 2013-10-08)

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.)?

**Tags:** cc.complexity-theory, ds.algorithms, optimization, sorting


---

## 2 answers

### Answer by username_3 on 2013-10-09. Score: 11 | Accepted answer

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$.

> **Comments:**
> **username_3**: ... mmm ... but what is the cost of C[x]=C[x]+1 ?!?  
> **username_4**: is there a problem with your answer? because it seems fine to me: you are saying we only care about array elements with values in $[M-n, M]$, so we can use counting sort. This works for the general problem whenever $|f(B[i], i) - B[i]| = O(n)$ for all $i$.  
> **username_0**: Thanks @Marzio. :) I slightly edited your answer for clarity. Feel free to roll-back my edit or edit further.  
> **username_0**: This solution seems to work also for any $f(x,i)$ where for all $x$ and $i\leq n$, $|f(x,i)-x| = O(n)$.  
> **username_3**: @username_0: edit is ok! I wrote the answer quickly and I was not even sure of its correcteness :-S  

---

### Answer by username_1 on 2013-10-09. Score: -1

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.

> **Comments:**
> **username_2**: What if A has n - 1 zeros and a single one? Then the answer is n, not 1.  
> **username_0**: Hi Yuval. There can be repeated numbers in $A$. As Grigory said the solution doesn't seem to work.  
> **username_0**: I think I see your idea for the lower-bound argument: given $A$ we can compute $B$ quickly using the query pairs made to $f$ by an algorithm solving the problem in time $o(n\lg n)$. We can make sure the algorithm queries $f$ on all $(B[i],i)$ but we cannot make sure it doesn't query other pairs. However we can set $f$ for other pairs to be a distinguishable value so we can discard those pairs.  

---

