6
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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)$.

Despite the ability to limit the analysis physically and end up with trivial observations, asymptotic analysis (without imposing those limits) does give practical information about algorithms. When we run them, we can certainly notice the difference between, say, Merge Sort and Bubble Sort - even when we have physically very small instances (even less than 1000).

So by speaking about algorithms in this more general (though not necessarily physically accurate) way, we get genuine information about how we can expect algorithms to perform based on how big the input is. More importantly it allows us to compare them.

From a different perspective, if we accept that all possible instances are smaller than some (really really big) constant, then all algorithms take constant time, what we then need to consider is what that constant is - if it amounts to longer than a few years, we haven't learnt anything useful to humans who only live a few years. If we lived longer than the life of the universe, then perhaps we wouldn't care about anything smaller than the size of the universe.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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 :) $\endgroup$ – rrampage Sep 24 '12 at 4:42
  • 1
    $\begingroup$ @rrampage If you consider real-world restrictions, every computer has a finite lifetime. Therefore, the runtime of any algorithm on any input is bounded by another constant, say 6 billion years (iirc about the timeframe left for our sun). (Busy beaver is not computable, so executing it is a lesser concern.) $\endgroup$ – Raphael Sep 24 '12 at 5:46
  • $\begingroup$ Apart from Raphael's comment, we can always make the same assumption that the input must be stored somewhere, regardless of the complexity of the algorithm, then everything disappears beneath the constant, and we don't see (mathematically) the behaviour that tells us something interesting about the problem in relation to others. $\endgroup$ – Luke Mathieson Sep 24 '12 at 6:09
  • $\begingroup$ @Raphael and Luke, have you read this blog post on Galactic algorithms? Puts what you have explained in perspective. Thanks for the clarifications :) $\endgroup$ – rrampage Sep 24 '12 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.