It was late at night, and the wind was howling outside – pounding its might against the brickwork of my house. I had a window of Sublime Text open as I usually do, watching the blinker flick on and off on the black, untitled canvas. A thought occurred to me: our fastest sorting algorithms tend to fall into the O(nlogn) classification, while nature it seems, can perform sorting at an O(n) classification.
The machine I had in mind, was in fact a centrifuge, which can sort trillions upon trillions of molecules by density without caring or even needing to know the position of each molecule. Its time complexity seemed to not care about how much substance was in the machine, which really got me thinking. Can this behaviour be mirrored in code?
I did what any programmer would do after writing some code and being unable to solve my problem – I posted the question to Stackoverflow, and then proceeded to not sleep for the next three hours while comment after comment emerged.
After a few hours, I had my answer. A few users had mentioned that a centrifuge operates in essence like parallel bubble sort, which has a time complexity of O(n). The key here however, is that computation and nature cannot be tricked. You still require computation to be performed on each of the nodes to execute a parallel bubble sort. Every molecule acts as if it has its own CPU calculating its position, as its order in space bends to the laws of nature. Although the sorting time is small, the computational costs are high!
But doesn’t a computer operate on the same principles of nature? If nature can sort something in O(n) time, then so can a computer (if you follow the logic that a computer follows natural laws in the same manner as our centrifuge, seeing as they are both physical machines).
Perhaps the missing piece here the strange world of quantum mechanics, such that nature exploits quantum mechanics to operate each of its computations. Most of our present computers on the other hand, are programmed and wired to operate via classical mechanics. Which led me to my last and final thought.
Can quantum computation sort items in the same way nature does over O(n) time? I’m not an expert and so, I don’t have the answer to this question. In fact, is quantum mechanics even needed to mirror the physics of a centrifuge? Perhaps it doesn’t matter at all, I mean O(nlogn) is quite close O(n). If you’re sorting a billion items, an O(n) algorithm would take a maximum of a billion steps, whereas an O(nlogn) algorithm could take potentially take nine times more steps to complete. It is longer, but not by an exponential factor or anything of that nature.
I wanted to also say that I realize the centrifuge is a bad example, seeing as it results in a gradient that is hard to verify. It was just the framework for my thought experiment. Regardless, nature is one hell of a computer. Maybe one day, we will able to fully exploit her deep, interesting secrets.