4 ms·

I'm going to provide an avenue for thinking about why the stick sorting example is problematic. Before starting, you have to specify the the size of the plate

I'm going to provide an avenue for thinking about why the stick sorting example is problematic. Before starting, you have to specify the the size of the plate / the sorting machine. Let's say it supports 10,000 sticks. I'm going to give you 20,000 sticks. Does your machine still solve the problem in O(N)? Nope, it's back to O(n log(n)). The issue with complexity theory is that it's for _arbitrarily large N_, and solutions that work intuitively for small N often run into walls, especially physical solutions. EDIT: BTW, I had to stop and think for a bit on that one. This question made me smile; it reminded me of why I enjoyed school. Great question, where the answer isn't obvious and elucidates something about the nature of complexity and how it disagrees with intuition.

gohrt 11y ago
You can build an arbitarily large sticky plate in linear time, before using the plate. It doesn't add a log(n) factor.
- parenthephobia 11y ago
  Well, I don't think that's true. Eventually, the plate will be higher density than the material available at the point of its construction, so it will need to take material from outside the plate's current area to fill it. As the plate extends further into lower-density regions, it will have to extend its materials gathering exercises further and further away from the actual construction site, so they'll take longer and longer to get there. Even if the plate is very low density indeed, eventually you'll run out of planet and have to start dismantling the moon - which is quite a long way away - unless the plate has a lower density than the volume of space the moon encloses.
solipsism 11y ago
I don't think this is the reason the sorting machine can beat O(nlogn). Just as any real sorting machine is limited in size, every real computer is limited as well. Just as the machine can't hold arbitrarily many (or arbitrarily large) sticks, your computer doesn't have enough memory to hold arbitrarily many (or arbitrarily large) numbers. Complexity theory is predicated on idealized computers (Turing machines with infinitely long tapes, or register machines able to hold infinitely large numbers).
Filligree 11y ago
But isn't this just radix sort, effectively? That's linear-time, no problem. There's no fundamental rule saying that sorting has to be O(n lg n), it's only sorting-by-comparison that needs O(N lg n) comparisons. Though I guess one might point out that, without direct (and infinitely precise!) comparisons, eventually you'll have enough sticks that you won't really be able to tell which is the largest.

gohrt 11y ago

You can build an arbitarily large sticky plate in linear time, before using the plate. It doesn't add a log(n) factor.

parenthephobia 11y ago
Well, I don't think that's true. Eventually, the plate will be higher density than the material available at the point of its construction, so it will need to take material from outside the plate's current area to fill it. As the plate extends further into lower-density regions, it will have to extend its materials gathering exercises further and further away from the actual construction site, so they'll take longer and longer to get there. Even if the plate is very low density indeed, eventually you'll run out of planet and have to start dismantling the moon - which is quite a long way away - unless the plate has a lower density than the volume of space the moon encloses.

solipsism 11y ago

I don't think this is the reason the sorting machine can beat O(nlogn). Just as any real sorting machine is limited in size, every real computer is limited as well. Just as the machine can't hold arbitrarily many (or arbitrarily large) sticks, your computer doesn't have enough memory to hold arbitrarily many (or arbitrarily large) numbers. Complexity theory is predicated on idealized computers (Turing machines with infinitely long tapes, or register machines able to hold infinitely large numbers).

Filligree 11y ago

But isn't this just radix sort, effectively? That's linear-time, no problem. There's no fundamental rule saying that sorting has to be O(n lg n), it's only sorting-by-comparison that needs O(N lg n) comparisons. Though I guess one might point out that, without direct (and infinitely precise!) comparisons, eventually you'll have enough sticks that you won't really be able to tell which is the largest.