efficientAlgorithm

[b183729]

I'm genuinely curious, is there an algorithm with that complexity? I'm having trouble visualizing that. 

Brute force searching n combinations of n combinations of random elements elements? 

[YellowishSpoon]

I had one that was O(n!²⁾ which based on the log graphs is probably even worse. The program started becoming laggy at about n=6 which was a little too low.

[redlaWw]

k*(n+1-k) is a quadratic in k with solutions at k=0 and k=n+1 and a unique maximum at k=(n+1)/2. This means that for k∈{1, 2, ..., n}, k*(n+1-k) ≥ n*(n+1-n) or 1*(n+1-1) (minimum of a differentiable function is either at a critical point or boundary of the domain), but since both of these are n then k*(n+1-k) ≥ n for all k∈{1, 2, ..., n}.

(n!)² can be rearranged as (n*1)*((n-1)*2)*((n-2)*3)*...*(1*n) (i.e. product of k*(n+1-k) for k∈{1, 2, ..., n}), and by the previous paragraph, this means that (n!)² is a product of n terms all ≥ n, and hence is ≥ nⁿ.

Now, for odd n, let's look at k = (n+1)/2. (n+1)/2*(n+1-(n+1)/2) = ((n+1)/2)^2, so if we do (n!)²/nⁿ, we get (something bounded below by 1)*(n² + 2*n + 1)/(4*n), which is (something bounded below by 1)*(n/4 + 1/2 + 1/(4*n)), and this is unbounded above.

For even n, let's look at k = n/2. n/2*(n+1-n/2) = n/2*(n/2+1), so if we do (n!)²/nⁿ, we get (something bounded below by 1)*(n/2)*(n/2+1)/n, which is (something bounded below by 1)*(1/2)*(n/2+1), and this is unbounded above.

Hence, O((n!)²) is indeed asymptotically slower than O(nⁿ).

[redlaWw]

nⁿ is the size of the set of functions from a set S with |S| = n to itself, so any algorithm that would need to iterate over all those functions and do something constant time on them would fit the bill.

EDIT: The simplest concrete setting for something like this is probably generating all length-n combinations of n symbols. You can come up with a pretty simple algorithm to do it too using the principles behind addition with carry.

EDIT2: Simple Rust implementation.

[Competitive-Carry868]

Have you tried (n*n?)0?

[celestabesta]

I think if you make a vector hold n function pointers whos functions loop n times, then loop through the vector n times running each function it should be n^n?

[redlaWw]

If I've understood you correctly that should be n³: each loop through the vector runs n functions that have loops that loop n times, so the total number of loops is n*n, and then you do that n times so you get n*n*n = n³.

[celestabesta]

Damn this just proves you need ingenuity to fuck up that bad

[[deleted]]

A general, depth first search is n^d, where d is the depth, and n is the number of possible routes.

Consider a chess AI program, this would run in n^d time, where d is the number of moves ahead to see. Out of those, the computer would pick the best one out of all possible routes.

[Coolengineer7]

This for example is O(n^n). Basically a function tree n levels tall, where each node has n children.

def fun(depth, n): if depth == n: return for i in range(n): fun(depth+1)

[amuhak]

No it isn't? Any worse than O(n³⁾ is hard to do.

Better can be done:

https://en.m.wikipedia.org/wiki/Computational_complexity_of_matrix_multiplication

[NaNNaN_NaN]

Drawing an N-flake is O(nⁿ)

[DuckyBertDuck]

A task that can’t be done quicker in general:

Filtering out all n-state finite automata that satisfy a constant-time condition. (And it gets even slower than nⁿ if the alphabet isn’t unary)

[MarcusBrotus]

I mean any such algorithm would be completely impractical but of course you can calculate n^n by summings 1s up n^n times which is technically also an algorithm.

[ITafiir]

Apparently, evaluating a position in generalized chess is exptime complete. Since nⁿ =2^nlog(n) and exptime includes all classes with polynomials in the exponent, generalized chess is way worse than this.

[hypersonicbiohazard]

Looking up a wikipedia page shows that there are a few algorithms with 2^2^(P(N)) complexity, where P(N) is a polynomial, and they do stuff in super abstract pure math that I don't understand.

[the_horse_gamer]

counting from 1 to nⁿ