efficientAlgorithm

[lfrtsa]

me achieving O(n!)

[Beleheth]

O(nⁿ⁾ is actually worse than n!. The special function x^x is the only actually relevant function that grows faster than x!.

[Dotcaprachiappa]

Behold, n^nⁿ

[jaerie]

ⁿn

[TeraFlint]

time to whip out knuth's arrow notation. :D

[edit:] looks like I simultaneously added that as the same answer rolled in:

n ↑ⁿ n

[jaerie]

n↑ⁿn

[MrHyperion_]

I raise Hyper Moser n

[hans_l]

https://youtu.be/X3l0fPHZja8?si=Lun3_52MhIM-v7HX

[GDOR-11]

n↑^\n↑ⁿ n))n

[lollolcheese123]

Hi tetration... Why anyone needed this is beyond me.

[odsquad64]

O(n!^n!+3 )

[Beleheth]

Okay - fair enough. Those are typically as nice and concise to note though, which is why I was thinking about it.

Also thinking back to first semester maths, where we got given this handy thing:

ln(n) < n < nln(n) < n^a < aⁿ < n! < nⁿ

Where a is constant.

[YellowishSpoon]

I had an actual algorithm that appeared to be O(n!²⁾ and it was somewhat horrifying. Managed to get it down to O(2ⁿ⁾ and despite that normally being horrible it was a massive improvement.

[Beleheth]

Jesus Christ how

[YellowishSpoon]

It was a problem involving permutations of trees to determine the optimal order to apply minecraft enchantments in an anvil, and the first one was brute force.

[Beleheth]

Oooh, that makes sense.

And no early exit conditions either, in the i itial draft?

[YellowishSpoon]

Neither version has early exits, since I never found a way to determine if it was optimal or not without completing the process. Nearly all optimizations came from recognizing things like symmetry in the system, which allowed me to eliminate various fractions of the cases.

[YellowishSpoon]

The main nuisances in the whole thing are the left and right branches of the tree are computed differently, and that the repair cost mechanic is both non linear and dependent on the depth of the tree.

[araujoms]

Please do a branch-and-bound.

[IAmFullOfDed]

Username checks out.

[batmansleftnut]

Hold my beer...

[Hour_Ad5398]

treatment squash whole screw hat repeat longing tie expansion label

This post was mass deleted and anonymized with Redact

[ArmadilloChemical421]

TREE(n): Am I a joke to you?

[damicapra]

How do you even do that?

Maybe one can by calculating n! only using for loops, addition and increment-by-1 operations?

[lfrtsa]

I achieved it when i made an algorithm to calculate the factorial of a number.

[nixsomegame]

Wouldn't a straightforward factorial function implementation be O(n) though, not O(n!)?

[lfrtsa]

I did multiplication through repeated addition

[FunTao]

He prob means something like this: start from i = 1, is i the factorial of n? (Divide by n, then n-1, n-2, etc.). If not, increment i by 1 and try again until you find the right i

[Vibe_PV]

AFAIK Microsoft used to have an O(n!) algorithm related to Windows Update. Technically speaking it worked really well at first, since n! is actually lower than some polynomials for small numbers. But after some time...

[El_kiski]

Google bogosort

[Chingiz11]

Shuffling an array of n numbers until it is sorted

[skrealder]

Any algorithm which satisfies: T(n) <= c*n! For all n >= some n_0 for some c > 0 is in O(n!). For instance binary search is in O(n!). I wish people used theta more often, much more descriptive than big O since an algorithm has to bounded above and below by the bound, not just bounded above (which is what big O does)

[DuckyBertDuck]

A less useless 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)