4 ms·
Linear time O(n) means that as you keep adding numbers to sort, the time taken is bounded by a linear function of how many numbers you have. Since there is an u
by mooshmoosh 7y ago
Linear time O(n) means that as you keep adding numbers to sort, the time taken is bounded by a linear function of how many numbers you have. Since there is an upper bound on the number of spaghetti strands you can hold in your hand, eventually you need to "Slam their lower sides on the table" in batches, and then merge sort the results. However because unlike in merge sort there is an upper bound on the size of the sub lists you use spaghetti sort will actually be O(n^2) instead of O(n log(n)).
If you ignore the usual meaning of linear time and restrict yourself to sorting lists of numbers that will fit in your hand, then spaghetti sort always runs in less time that however long it takes to sort the maximum amount of spaghetti you can hold in your hand. i.e. constant time.
- madmax96 7y agoYou can replace the hand with any device that holds the spaghetti. This really is an O(n) algorithm. Spaghetti sort seems to be an analogue variant of radix sort.
- FartyMcFarter 7y agoI suppose one could add a step 0 to the algorithm: 0: Manufacture a pair of hands big enough to hold all the spaghetti you'll need in the later steps. Does this step take linear time as well?
- madmax96 7y agoDoes it take O(n) time to manufacture computer memory? I don’t know, but it doesn’t affect the runtime of algorithms.
- FartyMcFarter 7y agoBut many sorting algorithms work in-place, so they don't require extra memory beyond a small O(1) or O(log n) amount for bookkeeping. When algorithms do require extra memory, they state this requirement as the space complexity.
- random_savv 7y agoI came here to write this comment. Glad somebody beat me to it! +1
- c3534l 7y agoIt is an ideal hand on an ideal table.
- jansan 7y agoTotally OT, but that reminds me of the first iPhone advertisements where they used exceptionally large hands to make the iPhone appear small. Quite funny if you think how smartphone sizes have developed since. This 2007 blog article is hilarious from today's view: https://nwinton.wordpress.com/2007/06/24/the-iphones-bigger-than-we-thought/ https://nwinton.wordpress.com/2007/06/24/the-iphones-bigger-...
- Enginerrrd 7y agoYeah, and IMO it's not even a good theoretical way to look at an analog computer. The hard part that will eat up time is differentiating the small differences between spaghetti to arbitrary precision. Analog systems still have to deal with signal to noise ratio issues, which affects the decision criteria here as in, "which one of these is the next longest?".
- chronial 7y agoAsymptotic times usually have assumptions on the problem size. On computers, you assume that memory access is constant time, which violates the laws of physics for arbitrarily large N.