11
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ ... mmm ... but what is the cost of C[x]=C[x]+1 ?!? $\endgroup$ – Marzio De Biasi Oct 9 '13 at 10:14
  • 1
    $\begingroup$ 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$. $\endgroup$ – Sasho Nikolov Oct 10 '13 at 2:23
  • $\begingroup$ Thanks @Marzio. :) I slightly edited your answer for clarity. Feel free to roll-back my edit or edit further. $\endgroup$ – Kaveh Oct 10 '13 at 4:47
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Kaveh Oct 10 '13 at 7:54
  • $\begingroup$ @Kaveh: edit is ok! I wrote the answer quickly and I was not even sure of its correcteness :-S $\endgroup$ – Marzio De Biasi Oct 10 '13 at 14:07
-1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What if A has n - 1 zeros and a single one? Then the answer is n, not 1. $\endgroup$ – Grigory Yaroslavtsev Oct 9 '13 at 5:07
  • $\begingroup$ Hi Yuval. There can be repeated numbers in $A$. As Grigory said the solution doesn't seem to work. $\endgroup$ – Kaveh Oct 9 '13 at 5:48
  • $\begingroup$ 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. $\endgroup$ – Kaveh Oct 9 '13 at 5:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.