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 -~----------~----~----~----~------~----~------~--~---
