# Upper-bounding the number of comparisons for Sorting to $\Theta(n)$ using a physically big number like Number of Particles in the Universe

I recently read an article Scott Aaronson - Big Numbers . That has made me think about the effective upper-bound for sorting.

According to the article, some of the big numbers like the number of particles in the universe and age of universe in milliseconds are less than $10^{100}$.

In any realistic computational device, the data to be sorted will have to be lesser than these numbers. (As otherwise, it would be impossible to store the numbers physically).

$\log_2(10^{100}) \approx 333$

Hence, if we take a number $C > 333$, we can show that number of steps required for sorting an input of size $n$ will always be lesser than $Cn$

This makes sorting an $O(n)$ time operation using algorithms like QuickSort or HeapSort.

Is there a point I've wrongly considered while making this assumption?

Should we consider physical constraints while analyzing algorithms? If not, why?

The reasoning is not wrong as such, but applying such constraints tends to make asymptotic analysis meaningless; for example we could simply choose $C' = 10^{100}$, and as all inputs are smaller than this, every algorithm is $O(1)$.
• Does the kind of input have any significance on the constants? Example the $C'$ mentioned in your answer may fail miserably for a faster growing function (think Busy Beaver). In case of Sort, we can take an (reasonably reasonable) assumption that the data must be stored somewhere. Ergo, the max data size must be lesser than the total number of particles in the universe (assuming that we can store "1 object" per particle). The same may not be said for other algorithms like say the N-CNF SAT problem or a Vertex-cover. Please clarify regarding this. Thanks :) – rrampage Sep 24 '12 at 4:42