ur right it does come o(n^2) as search is carried out n times On 8/16/06, Lego Haryanto <[EMAIL PROTECTED]> wrote: > > That's still an O(n^2) ... I believe your word "traversing" is O(n) by > itself ... And you're going to be traversing to the end of the list for each > insertion. > > > > > On 8/15/06, akshay ranjan <[EMAIL PROTECTED]> wrote: > > > > the link is not being sorted the elemnts are being read frm the array > > and inserted at the end of the list ( not sorting ). while traversing > > to end of the list jst chk if the element is already present in the > > list > > > > On 8/16/06, Vishal <[EMAIL PROTECTED]> wrote: > > > The simple way would be (for random numbers scenario) to sort the array > - > > > O(n log n) - and then traverse through the array to find the repeated > > > element - O(n). > > > The creation of link list is nothing but insertion sort, which is > O(n^2). > > > > > > ~Vishal > > > > > > > > > On 8/15/06, akshay ranjan <[EMAIL PROTECTED]> wrote: > > > > > > > > Not sure About the soln. but here goes > > > > > > > > Create a link list > > > > The node contains the number along with the list pointer. while > > > > creating the list impose a condition on insertion to chk for > > > > repetion.. i.e while traversing the list chk if the element is already > > > > inserted or not .given that n-1 are unique numbers and 1 no. repeats > > > > only , each elt will keep on being insertwed at end of the list while > > > > at the repeated element u could print the element and exit > > > > > > > > On 8/16/06, Lego Haryanto < [EMAIL PROTECTED]> wrote: > > > > > > > > > > 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) > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > -- > 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 -~----------~----~----~----~------~----~------~--~---
