<p>The folklore analysis of spaghetti sort <em>assumes</em> a model where one can extract the longest noodle <em>in constant time</em>, 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.</p>

<p>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?!</p>

<p>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.</p>

CC BY-SA 3.0
2011-06-20T09:11:41.513Z
Not to mention that pasta length is encoded in unary!
MassimoLauria
CC BY-SA 3.0
2011-06-20T16:00:21.473Z
It is?  I would have said the lengths are "encoded" as abstract real numbers, and not using bits at all.
Jeffε
CC BY-SA 3.0
2011-06-20T20:51:54.327Z
I agree that it is important to discard "noise" used to describe the setup as long as it does not directly represent computational activity being done on the input, but I believe that the process of extracting the rod that has stopped your hand is not just an artifact of the problem description but represents real computation at least to the extent the entire experiment does and thus needs to be accounted for in the complexity analysis, in fact we should be able to assume arbitrarily large hands and/or arbitrarily thin rods of pasta and have the complexity analysis remain the same regardless
mmmspaghetti
CC BY-SA 3.0
2011-06-20T20:51:54.327Z
of the number of rods (otherwise what is the point of using asymptotic bound notation in the first place?) As for the pastamagnetic plate extraction method - either this plate would be of fixed size which would require moving it to the rod at some time cost above O(1) per rod-to-be-extracted or it would be large enough to cover the whole pasta-plane but then we would have the computational cost of identifying a pasta rod on an otherwise empty n-sized plate and if we can assume this to be O(1) why not assume that picking the longest rod on a plate with many other rods is just as easy?
mmmspaghetti
CC BY-SA 3.0
2011-06-21T00:55:23.957Z
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.
MassimoLauria
CC BY-SA 3.0
2011-06-21T03:35:09.193Z
You're thinking too hard.  Spaghetti sort is a *joke*.
Jeffε
CC BY-SA 3.0
2011-06-21T03:59:25.070Z
TCS StackExchange. Taking jokes seriously since 2010.

;)
Daniel Apon
CC BY-SA 3.0
2011-06-22T01:00:11.070Z
Yes I definetly am thinking about this too hard and taking it way too seriously :)
but am I thinking about it *wrong* ? that is - is there a reason why  spaghetti sort can not be dismissed as essentially a tautology under the O(1)-extraction assumption ?

Anyway as I mentioned I`v lost access to the temporary user used to post the original question so if people feel like it`s a waste of everyone`s time feel free to ask the moderators to close it.
mmmspaghetti
CC BY-SA 3.0
2011-06-22T11:05:17.620Z
So I think what you mean is that they *should* be encoded in unary, but they are encoded in some sort of mythical pasta base, which is another completely unreasonable aspect of the model.
Andrew D. King
CC BY-SA 3.0
2011-06-22T12:45:03.447Z
@Andrew Do you mean that under the sensor model polling would take O(n) per rod ? or do you mean O(1) per rod and O(n) for the entire process - which can also be reasonable in the same way that the cost of adding two n-bit numbers can be assumed O(1) by using n-bit adder circuits but this would not imply an O(1) algorithm for the general problem of computing the sum of two n-bit numbers. (I dont argue with JɛﬀE that for fixed small n the original analysis is correct, just that it makes the whole notion pointless and precludes it from being a "general sorting algorithm" in any meaningfull way)
mmmspaghetti
CC BY-SA 3.0
2011-06-23T20:02:49.417Z
*...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.
Jeffε
CC BY-SA 3.0
2011-06-24T19:21:54.827Z
" Yes. That's the joke." - Right, except that its not presented as a joke in the wikipedia entry I linked to at the original question which states that "Spaghetti sort is a linear-time, analog algorithm for sorting a sequence of items"
mmmspaghetti
CC BY-SA 3.0
2011-06-20T05:45:10.613Z
2011-06-20T05:45:10.613Z
Jeffε
<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2011-06-19T13:33:33.537Z
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
mmmspaghetti
CC BY-SA 3.0
2011-06-19T14:40:43.113Z
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).
Ashley Montanaro
CC BY-SA 3.0
2011-06-19T15:10:17.077Z
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)
mmmspaghetti
CC BY-SA 3.0
2011-06-19T15:25:26.547Z
@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…
Ale De Luca
CC BY-SA 3.0
2011-06-19T15:30:46.873Z
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
mmmspaghetti
CC BY-SA 3.0
2011-06-22T11:07:11.067Z
Consider the reasonable model that your hand would require $n$ sensors to decide which of the $n$ pieces it was touching.  Then either polling takes $O(n)$ time, or you are making the model kind of complicated.
Andrew D. King
CC BY-SA 3.0
2011-06-22T13:26:10.760Z
Yes I did mean @mmmspaghetti, sorry Ashley :)
Ale De Luca
CC BY-SA 3.0
2011-06-19T13:26:04.163Z
2011-06-19T13:26:04.163Z
Ale De Luca
<h3>Just to continue the joke ...</h3>

<p>... we can simplify the spaghetti sort if we consider a 2D section of the <em>kitchen</em> (<em>spaghetti</em> are a bunch of $N$ segments, the <em>table</em> is a segment of length $W$, the <em>hand</em> is a segment, the <em>kitchen</em> 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:</p>

<pre><code>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
</code></pre>

<p><img src="https://i.sstatic.net/0YaTZ.jpg" alt="Spaghetti sort in 2D"></p>

<p>Suppose we start measuring time from step B ...</p>

<blockquote><b>what is the REAL time complexity of the spaghetti sort</b>?
</blockquote>

<p>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!!!).</p>

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

<p>So the total time of the spaghetti sort is:</p>

<p>$T = \sqrt{ \frac{2H}{g}} + \frac{H}{c} + N \times \frac{2H}{c}$</p>

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

<ul>
<li>suppose $W$ = 3 meters = 3000 millimeters ... 3000 / 8bits = 250 ... ok, a <strong>375x375 byte array is enough</strong></li>
</ul>

<p>... now we need a fast computer ... that can scan 375 bytes in:</p>

<ul>
<li>(3 meters) / (300000000 meters/sec) = 0,00000001 sec ... ok an old 100Mhz <strong>Intel486 is enough</strong></li>
</ul>

CC BY-SA 3.0
2011-06-24T09:00:59.160Z
2011-06-24T09:14:58.213Z
2011-06-24T09:14:58.213Z
Marzio De Biasi
<p><strong>Spaghetti sort is at least $O(p)$ where $p$ is the length of the
longuest spaghetto.</strong></p>

<p>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.</p>

CC BY-SA 3.0
2015-06-10T08:12:38.303Z
@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.
babou
CC BY-SA 3.0
2015-06-09T15:25:03.120Z
2015-06-09T15:25:03.120Z
babou
<p>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.</p>

<p>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. </p>

<p>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.</p>

CC BY-SA 3.0
2011-06-23T20:04:16.297Z
"Clearly"??  Really?  Why not?  Care to justify your intuition?
Jeffε
CC BY-SA 3.0
2011-06-23T17:00:26.207Z
2011-06-24T00:49:57.550Z
2011-06-24T00:49:57.550Z
David Harris
<p>I`m referring to the notion described here: <a href="http://en.wikipedia.org/wiki/Spaghetti_sort" rel="noreferrer">http://en.wikipedia.org/wiki/Spaghetti_sort</a></p>

<p>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.</p>

CC BY-SA 3.0
2015-05-23T22:10:07.450Z
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.
David Lilljegren
CC BY-SA 3.0
2016-07-06T14:17:13.150Z
I think spaghetti sort is $O(n^2)$ time because it requires $n^2$ time to make a horizontal plate of $n^2$ size.
noɥʇʎԀʎzɐɹƆ
<cc.complexity-theory><ds.algorithms><sorting>
is "spaghetti sort" really O(n) (even as a thought experiment) ?
mmmspaghetti
# is "spaghetti sort" really O(n) (even as a thought experiment) ?

(Asked by: username_0 on 2011-06-19)

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.

**Tags:** cc.complexity-theory, ds.algorithms, sorting
> **Comments:**
> **username_1**: 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.  
> **username_2**: I think spaghetti sort is $O(n^2)$ time because it requires $n^2$ time to make a horizontal plate of $n^2$ size.  

---

## 5 answers

### Answer by username_3 on 2011-06-20. Score: 26

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.

> **Comments:**
> **username_4**: Not to mention that pasta length is encoded in unary!  
> **username_3**: It is?  I would have said the lengths are "encoded" as abstract real numbers, and not using bits at all.  
> **username_0**: I agree that it is important to discard "noise" used to describe the setup as long as it does not directly represent computational activity being done on the input, but I believe that the process of extracting the rod that has stopped your hand is not just an artifact of the problem description but represents real computation at least to the extent the entire experiment does and thus needs to be accounted for in the complexity analysis, in fact we should be able to assume arbitrarily large hands and/or arbitrarily thin rods of pasta and have the complexity analysis remain the same regardless  
> **username_0**: of the number of rods (otherwise what is the point of using asymptotic bound notation in the first place?) As for the pastamagnetic plate extraction method - either this plate would be of fixed size which would require moving it to the rod at some time cost above O(1) per rod-to-be-extracted or it would be large enough to cover the whole pasta-plane but then we would have the computational cost of identifying a pasta rod on an otherwise empty n-sized plate and if we can assume this to be O(1) why not assume that picking the longest rod on a plate with many other rods is just as easy?  
> **username_4**: 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.  
> **username_3**: You're thinking too hard.  Spaghetti sort is a *joke*.  
> **username_5**: TCS StackExchange. Taking jokes seriously since 2010.  ;)  
> **username_0**: Yes I definetly am thinking about this too hard and taking it way too seriously :) but am I thinking about it *wrong* ? that is - is there a reason why  spaghetti sort can not be dismissed as essentially a tautology under the O(1)-extraction assumption ?  Anyway as I mentioned I`v lost access to the temporary user used to post the original question so if people feel like it`s a waste of everyone`s time feel free to ask the moderators to close it.  
> **username_6**: So I think what you mean is that they *should* be encoded in unary, but they are encoded in some sort of mythical pasta base, which is another completely unreasonable aspect of the model.  
> **username_0**: @Andrew Do you mean that under the sensor model polling would take O(n) per rod ? or do you mean O(1) per rod and O(n) for the entire process - which can also be reasonable in the same way that the cost of adding two n-bit numbers can be assumed O(1) by using n-bit adder circuits but this would not imply an O(1) algorithm for the general problem of computing the sum of two n-bit numbers. (I dont argue with JɛﬀE that for fixed small n the original analysis is correct, just that it makes the whole notion pointless and precludes it from being a "general sorting algorithm" in any meaningfull way)  
> **username_3**: *...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.  
> **username_0**: " Yes. That's the joke." - Right, except that its not presented as a joke in the wikipedia entry I linked to at the original question which states that "Spaghetti sort is a linear-time, analog algorithm for sorting a sequence of items"  

---

### Answer by username_7 on 2011-06-19. Score: 3

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.

> **Comments:**
> **username_0**: 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  
> **username_8**: 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).  
> **username_0**: 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)  
> **username_7**: @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…  
> **username_0**: 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  
> **username_6**: Consider the reasonable model that your hand would require $n$ sensors to decide which of the $n$ pieces it was touching.  Then either polling takes $O(n)$ time, or you are making the model kind of complicated.  
> **username_7**: Yes I did mean @mmmspaghetti, sorry Ashley :)  

---

### Answer by username_9 on 2011-06-24. Score: 2

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


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


---

### Answer by username_10 on 2015-06-09. Score: 1

**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.

> **Comments:**
> **username_10**: @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.  

---

### Answer by username_11 on 2011-06-23. Score: 0

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.

> **Comments:**
> **username_3**: "Clearly"??  Really?  Why not?  Care to justify your intuition?  

---

