Is it possible to make a O((n!)!) complexity algorithm?

Question

I can't imagine how such an algorithm would be constructed.

Would the algorithm "for every permutation of N elements, brute-force the traveling salesman problem, where the edges are decided by the order of the elements" have such a complexity?

Answer 1

Here's your algorithm!

import math

def eat_cpu(n):
    count = 0
    for _ in xrange(math.factorial(math.factorial(n))):
        count += 1
    return count

eat_cpu(4)

It is a function that calculates (n!)! using the method of incrementation. It takes O((n!)!) time.

---

Actually, upon reflection, I realized that this algorithm is also O((n!)!):

def dont_eat_cpu(n):
    return 0

because O is an upper bound. We commonly forget this when throwing O(...) around. The previous algorithm is thus Theta((n!)!) in addition to being O((n!)!), while this one is just Theta(1).

Answer 2

Enumerating all partitions of a set is O(n!). Now, all permutations of all partitions of a set will be O((n!)!), although the example is a bit artificial. Now, to come up with a useful algorithm it's a totally different story. I am not aware of any such algorithm, and in any case its scaling will be absolutely awful.

Answer 3

You can do better than that - there are known to be problems that require 2^2^(p(n)) time to solve - see http://en.wikipedia.org/wiki/2-EXPTIME - and it appears that these problems are not completely artificial either: "Generalizations of many fully observable games are EXPTIME-complete"