Well it is possible with a constraint that ur linked list is maintained sorted. Google more on Skiplist. It is a randomized probabilistic algorithm.
Regards, Sumedh On 6/11/08, Douglas Diniz <[EMAIL PROTECTED]> wrote: > Well, if you have a classic linked list, O(n) is the best for you. But you > can do better if you have a sorted linked list. In every node keep a vector > of pointers for all other nodes. Then you can simulate a binary search. > > On Wed, Jun 11, 2008 at 12:11 PM, Geoffrey Summerhayes <[EMAIL PROTECTED]> > wrote: > >> >> >> >> On Jun 11, 3:25 am, "zee 99" <[EMAIL PROTECTED]> wrote: >> > On 6/11/08, Mohammad Moghimi <[EMAIL PROTECTED]> wrote: >> >> On Wed, Jun 11, 2008 at 10:03 AM, zee99. 99 <[EMAIL PROTECTED]> wrote: >> >>> >> >>> is there any algo that can search a linked list in less than O(n) time >> >> >> >> No, I think O(n) is the best method one can use >> > >> > is this the best one even if the list is sorted ( or any other >> > constraint >> > like this is applied ) ?? >> > >> >> The only advantage to a sorted list is that you can often >> abandon the search early if the element you are looking for >> isn't in the list. This can give you a speed advantage over >> an unsorted list, but it is still O(n). >> >> --- >> Geoff >> >> > >> > > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
