Combinatorial Explosion!
The other day I hit a combinatorial explosion when using Haskell's nub function. Whilst I knew it was \( O(n^2) \) I thought my \( n \) (~28,000) wasn't big enough to cause a problem. Turns out it was...
Therefore to get a better feel for the size of the numbers involved for \( O(n^2) \) and various other common big O growth rates I've built a table comparing the values. Enjoy!
\( n \) | \( \log \log n \) | \( \log n \) | \( \sqrt n \) | \( n \log n \) | \( n^2 \) | \( n^3 \) | \( 2^n \) | \( n! \) |
---|---|---|---|---|---|---|---|---|
2 | 0 | 1 | 2 | 2 | 4 | 8 | 4 | 2 |
5 | 2 | 3 | 3 | 12 | 25 | 125 | 32 | 120 |
10 | 2 | 4 | 4 | 34 | 100 | 1,000 | 1,024 | 3,628,800 |
20 | 3 | 5 | 5 | 87 | 400 | 8,000 | 1,048,576 | 2.43x10^{18} |
50 | 3 | 6 | 8 | 283 | 2,500 | 125,000 | 1.12x10^{15} | 3.04x10^{64} |
100 | 3 | 7 | 10 | 665 | 10,000 | 1,000,000 | 1.26x10^{30} | 9.33x10^{157} |
200 | 3 | 8 | 15 | 1,529 | 40,000 | 8,000,000 | 1.60x10^{60} | 7.88x10^{374} |
500 | 4 | 9 | 23 | 4,483 | 250,000 | 1.25x10^{8} | 3.27x10^{150} | 1.22x10^{1134} |
1,000 | 4 | 10 | 32 | 9,966 | 1,000,000 | 1.00x10^{9} | 1.07x10^{301} | 4.02x10^{2567} |
2,000 | 4 | 11 | 45 | 21,932 | 4,000,000 | 8.00x10^{9} | 1.14x10^{602} | 3.31x10^{5735} |
5,000 | 4 | 13 | 71 | 61,439 | 25,000,000 | 1.25x10^{11} | 1.41x10^{1505} | 4.22x10^{16325} |
10,000 | 4 | 14 | 100 | 132,878 | 1.00x10^{8} | 1.00x10^{12} | 1.99x10^{3010} | 2.84x10^{35659} |
20,000 | 4 | 15 | 142 | 285,755 | 4.00x10^{8} | 8.00x10^{12} | 3.98x10^{6020} | 1.81x10^{77337} |
50,000 | 4 | 16 | 224 | 780,483 | 2.50x10^{9} | 1.25x10^{14} | 3.16x10^{15051} | 3.34x10^{213236} |
100,000 | 5 | 17 | 317 | 1,660,965 | 1.00x10^{10} | 1.00x10^{15} | 9.99x10^{30102} | 2.82x10^{456573} |
200,000 | 5 | 18 | 448 | 3,521,929 | 4.00x10^{10} | 8.00x10^{15} | 9.98x10^{60205} | 1.42x10^{973350} |
500,000 | 5 | 19 | 708 | 9,465,785 | 2.50x10^{11} | 1.25x10^{17} | 9.95x10^{150514} | 1.02x10^{2632341} |
1,000,000 | 5 | 20 | 1,000 | 19,931,569 | 1.00x10^{12} | 1.00x10^{18} | 9.90x10^{301029} | 8.26x10^{5565708} |