7
$\begingroup$

I`m referring to the notion described here: http://en.wikipedia.org/wiki/Spaghetti_sort

In the analysis section the author admits that considering it to be O(n) requires the assumption that the act of identifying and then removing the longest spaghetti rod which has stopped your hand from descending further is an O(1) rather than an O(n) or O(logn) operation - this seems to me a rather unreasonable assumption especially if many rodes of relatively simillar height exist. Alternatively it seems equivalent to assuming that one can pick the longest rode from a heap of rodes arbitrarily spread on a table at O(1) without going through the "leveling" procedure at all.

Improve this question
$\endgroup$
2
  • $\begingroup$ How about a laser moving down vertically. It could measure the horizontal position of each spaghetti it hits i.e. the index, while the lasers vertical position measures the height of the spaghetti. When a spaghetti is hit it either gets annihilated, become laser transparent or simply falls down. $\endgroup$
    – David Lilljegren
    May 23, 2015 at 22:10
  • $\begingroup$ I think spaghetti sort is $O(n^2)$ time because it requires $n^2$ time to make a horizontal plate of $n^2$ size. $\endgroup$
    – noɥʇʎԀʎzɐɹƆ
    Jul 6, 2016 at 14:17

5 Answers 5

Reset to default
25
$\begingroup$

The folklore analysis of spaghetti sort assumes a model where one can extract the longest noodle in constant time, perhaps by lowering a horizontal plate ("hand") over the vertical noodles until it stops, and then extracting the noddle touching the plate. (Apparently the plate is pastamagnetic.) Within this perfectly well-defined theoretical model, the analysis is clean and obviously correct.

So is the pastamagnetic-plate model reasonable? For up to a few hundred strands of spaghetti, sure. Beyond that, obviously not. So should we make the model more reasonable by taking the physical costs of moving the plate, sensing collisions, or choosing the right noodle? What about the (nonzero!) physical cost of keeping all the noddles vertical (or at least parallel), and keeping the sensing plate and the table horizontal (or at least parallel to each other but not the noodles)? Should we worry about the measuring process causing micro-fractures that change the exact length of the noddles, or the implication from quantum mechanics that there is no such thing as "exact length"? Holy crap, is the spaghetti-sorting problem even well-defined?!

No, this way lies madness. The original theoretical analysis is predictive within the context for which the algorithm was designed — manually sorting a handful of pasta #8. That the analysis does not generalize to significantly larger values of $n$ or other types of pasta does not make the analysis "incorrect". It merely limits its scope.

Improve this answer
$\endgroup$
12
  • 1
    $\begingroup$ Not to mention that pasta length is encoded in unary! $\endgroup$
    – MassimoLauria
    Jun 20, 2011 at 9:11
  • 5
    $\begingroup$ My point is that the running time of placing the hand on the top of the spaghetti set is polynomial in the length of the longest spaghetto. This is similar to the situation of an algorithm which works in time polynomial in the unary representation of inputs. $\endgroup$
    – MassimoLauria
    Jun 21, 2011 at 0:55
  • 1
    $\begingroup$ You're thinking too hard. Spaghetti sort is a joke. $\endgroup$
    – Jeffε
    Jun 21, 2011 at 3:35
  • 4
    $\begingroup$ TCS StackExchange. Taking jokes seriously since 2010. ;) $\endgroup$
    – Daniel Apon
    Jun 21, 2011 at 3:59
  • 1
    $\begingroup$ ...just that it makes the whole notion pointless and precludes it from being a "general sorting algorithm" in any meaningful way — Yes. That's the joke. $\endgroup$
    – Jeffε
    Jun 23, 2011 at 20:02
3
$\begingroup$

I disagree (i.e., I agree with Wikipedia). The leveling procedure assures that in order to remove the longest rod, you just need to lower your hand until you touch something. I can't see why this would take longer if there are more spaghetti, or if you touch more than one at once; of course, for larger amounts of rods, you would need larger hands, but I think that's a reasonable assumption in the quantum computing analogue.

On the other hand, without leveling you would have to look at the spaghetti to pick to longest one; that of course takes much longer as the number of rods grows.

Improve this answer
$\endgroup$
7
  • $\begingroup$ The reason I believe that it will take more time with more rods (when done by a human) is that your brain would still have to scan a vision field of size proprotional to the surface of the hand to corellate the sense of touch to the physical location of the rode and direct anotherhand/tool to remove it $\endgroup$
    – mmmspaghetti
    Jun 19, 2011 at 13:33
  • 1
    $\begingroup$ It's worth noting that, contrary to the impression that one might get from Wikipedia, quantum computers cannot speed up sorting in the standard comparison model: there is a known lower bound of Omega(n log n) comparisons (see quant-ph/0102078). $\endgroup$
    – Ashley Montanaro
    Jun 19, 2011 at 14:40
  • $\begingroup$ Yes I am aware that this analogy does not adequately describe quantum computing - my question is actualy about the classical-analog setup as described in the wikipedia article. It feels problematic that an order-of-magnitude speedup in sorting could be achieved solely due to the ability to parallelize the comparisons via the "leveling" procedure and that every physical way of extracting the currently-longest rod should have some dependence on the input size thus still keeping the complexity of the overall procedure above O(n) $\endgroup$
    – mmmspaghetti
    Jun 19, 2011 at 15:10
  • $\begingroup$ @Ashley, I don't think eyes are needed for that sort-of-algorithm. Anyway, now that you point that out, larger hands would probably imply the need to distinguish among a larger amount of tactile sensations, so you have a point anyway… $\endgroup$
    – Ale De Luca
    Jun 19, 2011 at 15:25
  • $\begingroup$ I think you meant @me not @Ashley, but yeah vision is not required here, even by blind touch your brain would still be doing some trial-and-error computation which would depend on the number of rods vs tactile resolution $\endgroup$
    – mmmspaghetti
    Jun 19, 2011 at 15:30
2
$\begingroup$

Just to continue the joke ...

... we can simplify the spaghetti sort if we consider a 2D section of the kitchen (spaghetti are a bunch of $N$ segments, the table is a segment of length $W$, the hand is a segment, the kitchen is a $W \times W$ square box, $W \gg N$ ... and it is supposed to be large enough to contain the longest spaghetto). We start with an empty kitchen and we end with an ordered sequence of spaghetti ... the system evolves in this manner:

A) we put a table in the kitchen (an horizontal segment in the box)
B) we hold the spaghetti over the table (a sequence of vertical segments across the
   hand segment)
C) we let them fall on the table (here gravity + the table do some magic)
D) we start move the hand downward
E) when our hand touch a spaghetto it picks it up, and move it on the left
F) repeat D-E until the hand touches the table

Spaghetti sort in 2D

Suppose we start measuring time from step B ...

what is the REAL time complexity of the spaghetti sort?

Let $H = \frac{W}{2}$ be half of the kitchen width. Suppose we start with our hand at height $H$ over the table, suppose that the spaghetti are "stored" at distance $H$ on the table during the sort, and finally suppose that our hand moves at the speed of light $c$ (a good approximation for a cook!!!).

  • $B \rightarrow C$ (the table+gravity parallel sort) takes roughly $T_1 = \sqrt{ \frac{2H}{g}}$
  • the hand takes $T_2 = \frac{H}{c}$ to reach the table
  • each "spaghetti pick" takes $T_3 = \frac{2H}{c}$

So the total time of the spaghetti sort is:

$T = \sqrt{ \frac{2H}{g}} + \frac{H}{c} + N \times \frac{2H}{c}$

If we switch to the turing machine world, we can simulate the kitchen using a bidemensional array ...

  • suppose $W$ = 3 meters = 3000 millimeters ... 3000 / 8bits = 250 ... ok, a 375x375 byte array is enough

... now we need a fast computer ... that can scan 375 bytes in:

  • (3 meters) / (300000000 meters/sec) = 0,00000001 sec ... ok an old 100Mhz Intel486 is enough
Improve this answer
$\endgroup$
1
$\begingroup$

Spaghetti sort is at least $O(p)$ where $p$ is the length of the longuest spaghetto.

In order to sort spaghetti, you must level them onto a table. If you consider the longest spaghetto, it has to slide down until its bottom touches the table, at which point a reaction force will propagate from the bottom up so that the whole spaghetto stops, including its top end. But propagation from bottom to top cannot be faster than the speed of light, hence it has to be proportional to the length of the spaghetto.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ @anonymousCoward Yet another example of the utter stupidity of downvoting without saying why. Why oppose comments that do not bring information, while encouraging votes that do worse. This is both counter-productive and poor scientific education. My answer is actually very serious. Like perpetual motion machines, "physical algorithms" are likely to be bound by hidden cost that impact their complexity. It is useful to understand where limitations can come from, however strange. $\endgroup$
    – babou
    Jun 10, 2015 at 8:12
0
$\begingroup$

The key sticking point is that analysis of algorithms is about the evolution of abstract machines with respect to data. It does NOT apply to the evolution of physical systems. In the latter case, there is not really any systematic treatment of asymptotic cost with respect to the asymptotic size of the problem.

This in fact gets to the heart of the strong Church-Turing thesis, which equates the class of "efficiently computable physical processes" with the class of polynomial-time turing machines To formalize this, one would have to show that the evolution of any physical system is polynomial-time in the "size" of the system.

So, to return to the question of Spaghetti sort --- given a physical system with $n$ pasta, what is the time complexity of computably simulating the evolution of such a system? The number of particles in the simulation is $O(n)$ (to model the pasta), possibly more (depending on the number of particles needed to model the plate), there are at least $O(n)$ time steps (at the least, one time step is needed for each pasta removed), and each the number of interactions in each time-slice will be probably $O(n)$ or $O(n^2)$. So I would estimate that simulating this system will be at least $O(n^3)$, probably much more.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ "Clearly"?? Really? Why not? Care to justify your intuition? $\endgroup$
    – Jeffε
    Jun 23, 2011 at 20:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.