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?

  • 0
    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?2012-02-22
  • 0
    I fixed my post. My apologies.2012-02-22

1 Answers 1

2

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.

  • 0
    Maybe this should be a comment.2012-02-22
  • 0
    Why? It directly answers the question, and the answer is "No."2012-02-22
  • 0
    @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.2012-02-23
  • 0
    The original question specifies that the input array contains _real numbers_, so hashing is not possible.2012-02-23
  • 0
    @JeffE: Oops! Thanks.2012-02-23