2
$\begingroup$

Suppose that I have an unsorted array of real numbers $\{a_i\}_{i=1}^n$. We sorted it in ascending order and now we have array $\{b_i\}_{i=1}^n$. Let $N=\max\limits_{i=\overline{1..n-1}} |b_{i+1}-b_{i}|$

I want to know $N$, but if I will sort the array $\{a_i\}_{i=1}^n$ and then will find $N$, the complexity of all operation will be $\mathcal{O}\left(n\log n \right)$. It isn't fast enough.

Is it possible to find better way, without sorting?

$\endgroup$
2
  • $\begingroup$ Wait, what is $n$ here? The size of the array, or just an index into the array? If the former, then what is the max over? If the latter, then what is the running time in terms of? Are you just looking for the difference between the largest and second largest elements? $\endgroup$
    – JeffE
    Feb 22 '12 at 23:43
  • $\begingroup$ I fixed my post. My apologies. $\endgroup$
    – sas
    Feb 22 '12 at 23:50
3
$\begingroup$

In the Algebraic Decision Tree model, we can prove an $\Omega(n\log n)$ lower bound for your problem.

This follows because the Element Distinctness Problem has the same lower bound and can be reduced to your problem.

$\endgroup$
5
  • $\begingroup$ Maybe this should be a comment. $\endgroup$
    – Aryabhata
    Feb 22 '12 at 22:17
  • $\begingroup$ Why? It directly answers the question, and the answer is "No." $\endgroup$
    – JeffE
    Feb 22 '12 at 23:53
  • $\begingroup$ @JeffE: Thanks! It does, but somehow does not seem to be a complete answer. Perhaps there is a "reasonable" model where it is indeed $o(n\log n)$? For instance, for element uniqueness an expected $O(n)$ algorithm exists if we allow hashtables. I do tend to agree with you, hence chose to put it as an answer. $\endgroup$
    – Aryabhata
    Feb 23 '12 at 0:00
  • $\begingroup$ The original question specifies that the input array contains real numbers, so hashing is not possible. $\endgroup$
    – JeffE
    Feb 23 '12 at 14:08
  • $\begingroup$ @JeffE: Oops! Thanks. $\endgroup$
    – Aryabhata
    Feb 23 '12 at 16:43

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.