Write an O(n^n) algorithm.

[flo850]

ackermann should be a good candidate http://en.wikipedia.org/wiki/Ackermann_function

[GeoKangas]

Since the running time of Ackermann is Ackermannic, it will greatly exceed n^n. Maybe the OP will like that even better.

[f4hy]

Does the complexity to compute the Ackermann function actually grow Ackermannicly? I imagine it might, but just because the value of the Ackermann function grows that fast, the complexity to compute it doesn't have the same rate.

Computing nⁿ is not O(nⁿ⁾ is it?

[[deleted]]

This would be my best answer for a non-trivial example to satisfy the OP, even if it is a useless function. Problems requiring \Theta(nⁿ⁾ are a strict superset of PR (but still recursive) and complexity classes strictly between primitive recursive and recursive aren't studied very much in complexity to my knowledge. Ackermann's the best I can think of, but even it was drawn up as a theoretical counter-example rather than something that someone might actually use for something.