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?