May 15, 2006
Homework #7: Due Wed May 17 (More intense)
7.10 (write down how you became convinced)
7.12 (be sure that your proof of the correct big-O bound is solid)
Posted by tonglaga at May 15, 2006 04:15 PM
Question 7.14 asks us to come up with a new merge algorithm "without using an auxillary array", yet it later says "you hae to sort the whole array T[1..n] using only a fixed amount of ADDITIONAL storage."
So, if we ARE allowed to use a fixed amount of additional storage, how is that any different than using an auxillary array? As far as I can tell the normal merge algorithm uses two fixed-sized auxillary arrays.
Posted by: brockj at May 16, 2006 11:31 PM
The difference is that the size of the array used by normal merge sort depends on n, but the fixed-size additional storage does not depend on n.
Post a comment
Thanks for signing in, . Now you can comment. (sign out)(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)