@Popli : Bingo , that is what i was thinking and mentioned in my previous post......
On Wed, Jul 20, 2011 at 7:08 PM, Gaurav Popli <abeygau...@gmail.com> wrote: > i want to ask one thing...the way some are saying first check with 2 > then 4 and then 16....to reach at that place we are suppose to > traverse it and also hav eto put a condition say like count<n or > something...in this case also we are comparing so whats the > use....correct me if im wrong..... > > On Wed, Jul 20, 2011 at 6:58 PM, bittu <shashank7andr...@gmail.com> wrote: > > can be done in O(n) find tow nodes from starting position find two > > nodes p,q such that p < k & k < q as linked list is sorted we have to > > keep going on in right direction complexity will no less then O(N) as > > its linked list there is no notion of binary search sorted linked list > > think out why ? > > > > only think we can apply some logic to reduce the comparisons that's i > > also think will be gr8 improvement but approach sounds good if start > > comparing the nodes value using multiple of 2 fact .e.g. take an > > integer i=2^j & from j=0 to start comparing 2^0th node, 2^1th node, > > 2^2th node....2^jth node might be we are able to reduce the number of > > comparisons > > > > do notify me via gmail if i am wrong if u find difficulty in TC ? else > > happy learning > > > > if this would have been sorted array then we could have been solved it > > O(logn) suing same approach. > > > > > > Thanks > > Shashank Mani > > Computer Science > > Birla Institute of Technology, Mesra > > > > -- > > 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 > algogeeks+unsubscr...@googlegroups.com. > > 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Ankur Khurana Computer Science , 4th year Netaji Subhas Institute Of Technology Delhi. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.