Not sure about the line O(k * n) = O(n) ...
That's probably assuming the hash-table doesn't have collision, which pretty much is O(1). What if somehow the numbers are chosen so that a particular hashtable would endure so many collisions, ... the complexity can then be worst-case O(n^2) ...
On 8/15/06, ridvansg <[EMAIL PROTECTED]> wrote:
Hi, here is the solution.
1. Create a hashtable .
2. Go through the numbers inserting each into the hashtable. When
insert the number check if it already exists, if so - this is the
repeating number.
The complexity: O(k*n) = O(n)
--
Fear of the LORD is the beginning of knowledge (Proverbs 1:7)
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
