http://en.wikipedia.org/wiki/Skip_list hope it helps :)
On Fri, Mar 11, 2011 at 2:20 PM, kumar vr <[email protected]> wrote: > We can study about Skip list from wiki or so, > > Assuming that there are no duplicate elements, do we fetch anything > from the skp list? > Priya, > What is the complexity of binary search on skip list with and > without duplicate elements. > And in what way it would be better than arrays? > > The whole question asked is about binary search on linked list.. > Binary search is possible on Linked lists (In partucular a Sorted > Linked list). > The Complexity of it would be N/2+N/4+..+1 in worst case, which comes > to O(N). > > In case of binary search on array, the complexity is O(Log N). > Sorting of an array will take O(n log n). > > Can we discuss something on the time complexity of linked listes here. > > > > On Mar 11, 10:39 am, UTKARSH SRIVASTAV <[email protected]> > wrote: > > what is skip list > > > > On Fri, Mar 11, 2011 at 5:58 AM, priya mehta <[email protected] > >wrote: > > > > > > > > > > > > > use skip list:) > > > > > On Thu, Mar 10, 2011 at 2:31 PM, ravi teja <[email protected]> > wrote: > > > > >> @Utkarsh : > > > > >> Yeah , that is when you can access any element in O(1) time and the > > >> elements are sorted.This happens in a sorted array where you get an > overall > > >> complexisty of O(logn). > > > > >> -- > > >> You received this message because you are subscribed to the Google > Groups > > >> "Algorithm Geeks" group. > > >> To post to this group, send email to [email protected]. > > >> To unsubscribe from this group, send email to > > >> [email protected]. > > >> For more options, visit this group at > > >>http://groups.google.com/group/algogeeks?hl=en. > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to [email protected]. > > > To unsubscribe from this group, send email to > > > [email protected]. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > > > -- > > UTKARSH SRIVATAV > > CSE-3 > > B-TECH 2nd YEAR > > MNNIT ALLAHABAD > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
