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.
