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.

Given an integer N and an array of N real numbers (which you can compare and add/multiply/divide in O(1)), output 1 if there are two equal numbers and 0 else. This can easily be solved in O(N*log N) worst case time complexity, by sorting and then checking any two adjacent entries if they are equal. The question is: is there an algorithm that does this in o(N*log N) worst case time complexity? (notice the small omicron notation). I've been able to prove that there is no comparison-based algorithm that does this in o(N*log N) (by comparison-based I mean that you are not given the array, but only an orcale that takes as an input two given integers in the array and tells you in O(1) which of the two is bigger (or if they are equal). I can't seem to solve it in less, though. Does anyone know?

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

Moving my comment to an answer:

It is known that checking element distinctness requires $\Omega(n \log n)$ comparisons in the algebraic decision tree model.

Rough sketch: You can divide the topological space $A \subset {\mathbb R}^n$ of points with distinct coordinates into $n!$ connected components. After the algorithm has finished it has to know what is the connected component. Otherwise, it could not distinguish being in some component of $A$, and being outside $A$.

For details, see http://en.wikipedia.org/wiki/Element_distinctness_problem and lecture 6 at "Lower bounds in computer science" http://cs.dartmouth.edu/~ac/Teach/CS85-Spring08/lecnotes.pdf

share|improve this answer
add comment

Finding duplicates in a list is a standard application of hash tables. But any algorithm must be $\Omega(NM)$ in the worst case, because it takes that long simply to read the array of numbers. You're greatly skewing the analysis by accounting for $M$ in some cases, but neglecting it in a comparison-based algorithm.

share|improve this answer
    
I was trying to avoid talking about models, but I'll rephrase the question to avoid this. –  Ekuurh Apr 19 '12 at 14:16
    
@TomKalvari: Without an underlying model, your question is meaningless. What does time complexity even mean in that case? –  Aryabhata Apr 19 '12 at 14:41
    
As I wrote, all you can do is compare numbers and preform basic algebraic operations. @sdcvvc provided the full answer though, so thanks, but appereantly it's all been solved before. (I'm new in this site - how do I say sdcvvc's answer is the final one?) –  Ekuurh Apr 19 '12 at 19:29
    
If you count basic arithmetic operations as O(1), then a hash table solves the problem in O(N) average time, because both inserts and lookups are O(1). –  Hurkyl Apr 20 '12 at 2:09
    
Yea, I noticed, but in the computational model I'm referring to, all you can do is do basic arithmetic operations and compare in O(1). You can't access memory from a random hash function. –  Ekuurh Apr 20 '12 at 10:22
show 3 more comments

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.