4 ms·
Before reading, I thought they had found a faster sequence of disk transfers (stop the press etc) -- but it turns out the article is just about generating the s
by limmeau 17y ago
Before reading, I thought they had found a faster sequence of disk transfers (stop the press etc) -- but it turns out the article is just about generating the same sequence of moves in less time, given the C compilers of late-90s workstations.
- scscsc 17y agoHighly unlikely to happen, since the upper bound corresponds to a well-known lower bound.
- limmeau 17y agoYes, unless you find premises to drop, thus changing the problem. Sorting is Omega(n log n) under the premise that all you have is a computable ordering relation. Radix sort removes that premise and reaches a different lower bound. In the particular case of the Hanoi problem, I don't see droppable premises (except "you can only move one disk at a time" -- drop that and there may be an O(1) solution).