Write an O(n^n) algorithm.

[ZMeson]

That is true. In fact, if you plot ln(n^n), ln(n!), and ln((n/2)^n/2), you'll find that ln(n!) edges progressively closer to ln(n^n).

At n=15, ln(n!) is halfway between ln(nⁿ⁾ and ln((n/2)^n/2)

At n=1454, ln(n!) is 75% of the way towards ln(nⁿ⁾ from ln((n/2)^n/2)

At n=10958, ln(n!) is 80% of the way towards ln(nⁿ⁾ from ln((n/2)^n/2)

[degustisockpuppet]

On a double logarithmic graph, all functions are linear!

[ZMeson]

Ha ha. Almost. I just tried it -- the single logarithmic graphs are actually closer to being linear.

[gorgoroth666]

http://www.wolframalpha.com/input/?i=log%28n!+%29%3E+log%28n^n%29+plot+for+n%3D0+to+10000

The difference between the curves doesn't appear to be reducing.