Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

How to analyze an efficient algorithm?

Posted on 2008-06-16
7
Medium Priority
?
1,345 Views
Last Modified: 2008-08-28
Bob has a set A of n nuts and a set B of n bolts, such that each nut in A has a unique matching bolt in B.
Unfortunately, the nuts in A all look the same, and the bolts in B all look the same as well. The only kind of a comparison that Bob can make is to take a nut-bolt pair (a,b) such that a is in B, and test it to see if the threads of a are larger, smaller, or a perfect match with the threads of b. Describe and analyze an efficient algorithm for Bob to match up all of his nuts and bolts.
0
Comment
Question by:secondcup
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
7 Comments
 
LVL 31

Accepted Solution

by:
Frosty555 earned 672 total points
ID: 21795552
Well, the rigorous solution is to try every nut with every bolt, and use the ones that work, ignoring the extra information you have of knowing whether a nut is too small or too large for the bolt.

That would run in O(N^2) time. So when the question says "describe an efficient algorithm", it wants something better than the obvious.
0
 
LVL 74

Assisted Solution

by:sdstuber
sdstuber earned 664 total points
ID: 21795628
Compare bolt x with nut y.  If y is larger then put in "large" pile.  if y is smaller put in "small" pile.
continue until matching y is found.

Get bolt x2,  compare with y1.  if y1 is larger go to "small" pile and search.  dividing into small 1 and small 2.  If y1 is smaller then go to "large" pile and search, dividing into large 1 and large 2.

If not found in already searched piles, go to remainder of original pile of nuts.  again dividing into large and small.

get bolt x3,  compare to y2 and y1 to determine which of the prior semi-sorted nut piles to look through.  

continue through each bolt,  compare to previous bolt's nuts to try find smaller piles to search.  As you go through the bolts the piles should get smaller but more numerous with each being closer and closer to a full sort by size.

If you can get any kind of inter-bolt comparison or inter-nut comparison (which it sounds like you've already eliminated) then you can make it more efficient.  but if you can only compare bolts to nuts then I think semi-sorted piles is about as good as you'll get as it will let you derive a sorting that will help over a simple n^2 comparison
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 21795841
Is this an assignment ? How far did you get ? What are you unsure about ?
0
 
LVL 22

Assisted Solution

by:NovaDenizen
NovaDenizen earned 664 total points
ID: 21813978
Use partitioning.  The expected performance is exactly the same as quicksort.
0
 
LVL 18

Expert Comment

by:philipjonathan
ID: 21828481
The performance can be better than O(n^2), it should be O(n log n)
0

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: Nadia
Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
When there is a disconnect between the intentions of their creator and the recipient, when algorithms go awry, they can have disastrous consequences.
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Do you want to know how to make a graph with Microsoft Access? First, create a query with the data for the chart. Then make a blank form and add a chart control. This video also shows how to change what data is displayed on the graph as well as form…
Suggested Courses

722 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question