I just had a little too much free time a few days ago and made a simple comparison about two sorting algorithms, one had O(n^2) complexity and the other one had O(n*log(n)).
Here are the numbers:
For 100 000 000 000 numbers
10000000000000000000000 * 1(best programmer in the world) - operations for O(n^2) sorting
3654120904377 * 10 (constant factor due to bad programmer) - operations for O(n*log(n)) sorting
1000000000000 - seconds for O(n^2) sorting with a computer that makes 10 ^ 10 operations per second and the best programmer (c = 1)
7308.241808754 - seconds for O(n * log2(n)) sorting with a computer that makes 5 * 10 ^ 9 operations per second and a bad programmer (c = 10)
31 710 years -- O(n^2) for sorting
2h 1m 49s -- O(n*log(n)) for sorting
No comments:
Post a Comment