# Find a maximum of difference without sorting.

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?

-
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? – JeffE Feb 22 '12 at 23:43
I fixed my post. My apologies. – sas Feb 22 '12 at 23:50

In the Algebraic Decision Tree model, we can prove an $\Omega(n\log n)$ lower bound for your problem.
@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. – Aryabhata Feb 23 '12 at 0:00