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
    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
    @JeffE: Oops! Thanks.2012-02-23