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