Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I suppose that counting n elements should be linear time, right? It takes double time to count double number of elements. But in the real world, it is faster and O(1) to weigh elements and find out the total weight so in the real world you can count n elements O(1) just by putting all the elements on a scale and dividing by the weight of one elements.
Is my reasoning correct that physically it is possible to speed up a calculation by this trick, or am I mistaken?
Weighing elements works faster than counting them, because the scale is a fully parallel computing device. It sums the weighs of all elements in constant time. Of course you need an infinitely large scale if you want to talk about asymptotic runtimes. In practice your scale can only weigh a constant number of items at once, so your speedup is only a constant factor.
A related algorithm is Spaghetti sort.
You make an accurate but rather basic observation: complexities depend on the model of computation you assume. In your informally described model "the real world", some things may indeed work differently than they do for TMs. Be wary of making wrong assumptions, though.
Here, you change the problem. You move from "counting" to "computing total weight". These are only the same if all items have the same weight.
Keep in mind that you have to put the items on the scale first. Assuming you can only put constantly many things on the scale at a time, this makes your method take linear time as well. And that's assuming a scale with unlimited capacity, which you probably don't have. Simply counting items where they lie is probably faster and more energy efficient.
You're mistaken: it takes more than constant time to divide the total mass by the weight of a single object to compute the count.
Physical considerations, such as whether your scales can measure arbitrary weights or whether you can put arbitrary numbers of things on the scales at the same time (as mentioned by adrianN and Raphael) could maybe be swept under the carpet by just defining the computational model to allow that. But assuming that you can divide two arbitrarily long numbers in constant time seems to be a much bigger deal.
