How in the hell does anyone f— up so bad they get O(n!²)? 🤯 That’s an insanely quickly-growing graph.
Curious what the purpose of that algorithm would have been. 😅
You have two lists of size n. You want to find the permutations of these two lists that minimizes a certain distance function between them.
Surely you could implement this via a sorting algorithm? If you can prove the distance function is a metric and both lists contains elements from the same space under that metric, isn’t the answer to sort both?
It’s essentially the traveling salesman problem
Let me take a stab at it:
Problem: Given two list of length n, find what elements the two list have in common. (we assume that there are not duplicates within a single list)
Naive solution: For each element in the first list, check if it appears in the second.
Bogo solution: For each permutation of the first list and for each permutation of the second list, check if the first item in each list is the same. If so, report in the output (and make sure to only report it once).
lol, you’d really have to go out of your way in this scenario. First implement a way to get every single permutation of a list, then to ahead with the asinine solution. 😆 But yes, nice one! Your imagination is impressive.
Maybe finding the (n!)²th prime?
I guess, yeah, that’ll do it. Although that’d probably be yet one or a few extra factors involving n.
N00b. True pros accomplish O((n^2)!)
Your computer explodes at 4 elements
Did you write an algorithm to manually drag and drop elements?
Imagine if the algorithm were in Θ(n!²), that would be even worse
You mean omega, not theta
Also constant time is not always the fastest
plot twist to make it worse: you put in in an
onInputhook without even a debounceHow the fuck?!
Oh my god, that’s inefficient as hell.
It may be efficient, not scalable for sure
For me, my common result would be something like O(shit).
Wait… How can time ever not be constant? Can we stop time?! 😮
It has been a while since I have to deal with problem complexities in college, is there even class of problems that would require something like this, or is there a proven upper limit/can this be simplified? I don’t think I’ve ever seen O(n!^k) class of problems.
Hmm, iirc non-deterministic turing machines should be able to solve most problems, but I’m not sure we ever talked about problems that are not NP. Are there such problems? And how is the problem class even called?
Oh, right, you also have EXP and NEXP. But that’s the highest class on wiki, and I can’t find if it’s proven that it’s enough for all problems. Is there a FACT and NFACT class?
