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.43x1018 |
| 50 | 3 | 6 | 8 | 283 | 2,500 | 125,000 | 1.12x1015 | 3.04x1064 |
| 100 | 3 | 7 | 10 | 665 | 10,000 | 1,000,000 | 1.26x1030 | 9.33x10157 |
| 200 | 3 | 8 | 15 | 1,529 | 40,000 | 8,000,000 | 1.60x1060 | 7.88x10374 |
| 500 | 4 | 9 | 23 | 4,483 | 250,000 | 1.25x108 | 3.27x10150 | 1.22x101134 |
| 1,000 | 4 | 10 | 32 | 9,966 | 1,000,000 | 1.00x109 | 1.07x10301 | 4.02x102567 |
| 2,000 | 4 | 11 | 45 | 21,932 | 4,000,000 | 8.00x109 | 1.14x10602 | 3.31x105735 |
| 5,000 | 4 | 13 | 71 | 61,439 | 25,000,000 | 1.25x1011 | 1.41x101505 | 4.22x1016325 |
| 10,000 | 4 | 14 | 100 | 132,878 | 1.00x108 | 1.00x1012 | 1.99x103010 | 2.84x1035659 |
| 20,000 | 4 | 15 | 142 | 285,755 | 4.00x108 | 8.00x1012 | 3.98x106020 | 1.81x1077337 |
| 50,000 | 4 | 16 | 224 | 780,483 | 2.50x109 | 1.25x1014 | 3.16x1015051 | 3.34x10213236 |
| 100,000 | 5 | 17 | 317 | 1,660,965 | 1.00x1010 | 1.00x1015 | 9.99x1030102 | 2.82x10456573 |
| 200,000 | 5 | 18 | 448 | 3,521,929 | 4.00x1010 | 8.00x1015 | 9.98x1060205 | 1.42x10973350 |
| 500,000 | 5 | 19 | 708 | 9,465,785 | 2.50x1011 | 1.25x1017 | 9.95x10150514 | 1.02x102632341 |
| 1,000,000 | 5 | 20 | 1,000 | 19,931,569 | 1.00x1012 | 1.00x1018 | 9.90x10301029 | 8.26x105565708 |