Suppose you can solve this problem better than O(nlog(n) ) . This means that given an array you would be able to find the duplicate number quicker than O(nlog(n) ). Using the same algo you would be able to determine that there no duplicate numbers, since a search for the duplicate number would simply fail. This would mean that you have determined that all numbers are unique in time quicker than O(nlog(n) ). However this is not possible and leads to a contradiction.
Adak,
Usually when analysing an algorithm. The algorithm's worst case running time should be independent of the input to it.
-Dhyanesh
On 12/3/05, pramod <[EMAIL PROTECTED]> wrote:
I agree with Dhyanesh. This "counting" sort routine prescribed by Adak
fails when the numbers can be random.
Dhyanesh, I searched for "element uniqueness" and that problem is more
generic. It says to find if all the numbers are unique. But in my
problem it is known that exactly one number is duplicated (and exactly
once). So I am still hoping for a better solution than O(n log(n) ).
