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.
