Meng Lu's home page / blog / n-squared time complexity is really slow

A few numbers to illustrate how bad \mathcal{O}\left(N^2\right) time complexity is, just so the well known fact is more concrete. It does not take much to make it useless for practical purposes in the Big Data era.

The plot N/\log N vs. N, should illustrate how large the difference between the two growth rates \mathcal{O}\left(N^2\right) and \mathcal{O}\left(N \log N\right) really is: at some time scale, a computation with input size N = 10^6 can be computed within a day by \mathcal{O}\left(N \log N\right) but will take about two human lifetimes (about 50000 days) to do:

Comparison between O(N*lgN) and O(N^2) time complexities

Comments on this page are closed.
blog comments powered by Disqus