While sorting itself, algorithm can keep track of minimum difference between two consecutive elements found so far and the elements. This way time complexity is same as time complexity of sorting algorithm.
Space complexity also I think its O(1). On Wed, Sep 2, 2009 at 6:00 PM, Ralph Boland <[email protected]> wrote: > > > > On Sep 1, 7:05 am, ankur aggarwal <[email protected]> wrote: > > given a array of length n. find 2 number such that their differnce is > > minimum..... > > As already pointed out sorting and then comparing adjacent elements > gives you an O(n log n) algorithm. > If you have a likelyhood of duplicates then heapsort might be better > since the heap can be built in linear time and the sort phase can be > aborted if a duplicate element is found. Alternatively one could > put your elements into a set (using hashing) and stop immediately > if you discover a duplicate by adding an element to the set that is > already there (O(n) expected time to build the set). > > Ralph Boland > > > -- Dinesh Bansal The Law of Win says, "Let's not do it your way or my way; let's do it the best way." --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
