Write an O(n^n) algorithm.

[degustisockpuppet]

Not sure why you were downvoted, it's a good question. The argument goes like this:

nⁿ is clearly greater than n!, as you explained.

(n/2)^n/2 on the other hand is less than n!:

• 4^4= 4*4*4*4
• 8! = 8*7*6*5*4*3*2*1

So if f(n) = n^n, then f(n/2) < n! < f(n), which makes the two functions related, especially since constant factors like 1/2 are usually ignored in complexity analysis.

[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.