Currently, I'm learning to perform algorithm analysis using Big-O notation. In one resource I found the following problem:
The answer given is n^2 (n squared) with the following explanation:
The order of magnitude is correct, but the reasoning seems wrong. Imagine you have 2 toys and thus 4 pieces.
You just dropped a box of glass toys and n toys in the box broke in half. You'd like to match the halves of the toys so that you could glue them together, but the only way to tell whether two halves belonged to one toy is to physically pick up the two pieces and try to fit them together. Express how long this matching process will take in terms of n.
The answer given is n^2 (n squared) with the following explanation:
You have to compare every piece with every other piece. If you have 1 toy and it breaks in half, you have 1 comparison to make. If you have 2 toys and they both break in half there are 4 pieces and you have to do 6 comparisons. If you have 3 toys, there are 6 pieces and you have to do 15 comparisons. If you haveN/2
toys, you haveN
pieces and you have to doN-1 + N-2 + N-3 + ... + 1 =(N)(N-1)/2
comparisons. This isO(N^2).
The order of magnitude is correct, but the reasoning seems wrong. Imagine you have 2 toys and thus 4 pieces.
- Starting with a random piece, there are 3 other pieces to compare it with.
- In the worst case, the first two comparisons don't produce a match. This means however, that the third piece is necessarily a match.
- Once you have performed those two (incorrect) matches, and reassembled the first toy, the remaining two pieces don't need to be tested as they necessarily fit.
- If you add the steps to reassemble the toys (1 each), that gives a total of 4 matches for 2 toys.
Let's check this reasoning with three toys.
- 3 toys: A, B,C
- Broken in half into 6 pieces: A1, A2, B1, B2, C1, C2
- Take one piece to test: A1.
- In the worst case, all your first matches are wrong:
- A1-B1 , A1-B2, A1-C1, A1-C2
- Thus, it takes at most, 4 matches to match A1-A2 plus the step to reassemble A which gives 5 matches.
- Now, there are only two toys left (B & C) to match. From our previous reasoning we know that only 4 matches are necessary.
- This means it will take, at most, 9 matches to reassemble 3 toys.
If we perform this analysis for 4 toys, we'll find that it takes 7 matches to reassemble the first toy for a total of 16 matches.
In general, the pattern is n^2 (exactly) or O(n^2). This is what the answer stated, but the finer details of the answer seem off.
Comments
Post a Comment