You have m nuts and n bolts, Every unique nut is fit in every unique bolt, Suggest an effective algorithm for placing each nut in each bolt in less no. of passes?
Click for Solution

  • Warning: Illegal string offset 'name' in /home/prepdo6/gpl4you/discussquessub.php on line 681
    A sort the nuts and bolts list in order of ascending size in O(mlog(m)) and O(nlog(n)) times den one by one pick a nut from the sorted array and fit it into the bolts this process will take O(n) time so total time taken is O(nlog(n)) by the algo

    CpjJwWHV   Although the asymptotic complexity is O(NlogN) [assume N>=M] yet the hidden constant is somewhat larger as the total complexity is O(NlogN) + O(MlogM)+
    O(N). This constant can be improved.
    Here is the algorithm:
    1) Sort all nuts OR bolts (which ever is lesser in number). The complexity of this step is: O(XlogX) {where X = min(N,M) }

    2) Now take another set (the unsorted one) and do a binary search for its position in the sorted array(the other one). Thus you only need to sort one array in this
    case. Complexity of this step will be: O(YlogX) {where X is same as above & Y is max(N,M)}
    Overall complexity: O(XlogX) + O(YlogX) [X,Y are defined above]

    There is yet another way with complexity of O((N+M)log(N+M)) which goes like
    this: mix all nuts and bolts and sort the resulting mixture. Then in the resultant
    the bolt and its corresponding nut will appear adjacent to each other. This can be accomplished in O(N+M) time.

    Thank you.
    14 years ago

    Smiley
[Insert Code]