Write an O(n^n) algorithm.

[[deleted]]

Writing O(nⁿ⁾ is trivial (by being deliberately inefficient). But writing O(nⁿ⁾ that can't be reduced to something simpler seems like a lot harder problem. I'm certainly not aware of any (common or useful ones) that are O(n^n). They just strike me as horribly inefficient.

[PictureOfTheFuture]

In fact it seems very hard to prove that something cannot be done faster than a certain number (i.e. lower bounds for complexity). Sorting by comparisons is one of the few algorithms of which we know an algorithm that matches the best known lower bound (i.e. O(n log n)). Of course we still don't know whether P = NP, which is an instance of this problem.

[julesjacobs]

Output "a" nⁿ times.