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 <[email protected]> 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 [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.
