Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Maybe this should be a comment. –  Aryabhata Feb 22 '12 at 22:17
    
Why? It directly answers the question, and the answer is "No." –  JeffE Feb 22 '12 at 23:53
    
@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
    
The original question specifies that the input array contains real numbers, so hashing is not possible. –  JeffE Feb 23 '12 at 14:08
    
@JeffE: Oops! Thanks. –  Aryabhata Feb 23 '12 at 16:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.