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! \)
201224842
5233122512532120
10244341001,0001,0243,628,800
20355874008,0001,048,5762.43x1018
503682832,500125,0001.12x10153.04x1064
100371066510,0001,000,0001.26x10309.33x10157
20038151,52940,0008,000,0001.60x10607.88x10374
50049234,483250,0001.25x1083.27x101501.22x101134
1,000410329,9661,000,0001.00x1091.07x103014.02x102567
2,0004114521,9324,000,0008.00x1091.14x106023.31x105735
5,0004137161,43925,000,0001.25x10111.41x1015054.22x1016325
10,000414100132,8781.00x1081.00x10121.99x1030102.84x1035659
20,000415142285,7554.00x1088.00x10123.98x1060201.81x1077337
50,000416224780,4832.50x1091.25x10143.16x10150513.34x10213236
100,0005173171,660,9651.00x10101.00x10159.99x10301022.82x10456573
200,0005184483,521,9294.00x10108.00x10159.98x10602051.42x10973350
500,0005197089,465,7852.50x10111.25x10179.95x101505141.02x102632341
1,000,0005201,00019,931,5691.00x10121.00x10189.90x103010298.26x105565708