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
N00b. True pros accomplish O((n^2)!)
After all these years I still don’t know how to look at what I’ve coded and tell you a big O math formula for its efficiency.
I don’t even know the words. Like is quadratic worse than polynomial? Or are those two words not legit?
However, I have seen janky performance, used performance tools to examine the problem and then improved things.
I would like to be able to glance at some code and truthfully and accurately and correctly say, “Oh that’s in factorial time,” but it’s just never come up in the blue-collar coding I do, and I can’t afford to spend time on stuff that isn’t necessary.
A quadratic function is just one possible polynomial. They’re also not really related to big-O complexity, where you mostly just care about what the highest exponent is:
O(n^2) vs O(n^3)
.For most short programs it’s fairly easy to determine the complexity. Just count how many nested loops you have. If there’s no loops, it’s probably
O(1)
unless you’re calling other functions that hide the complexity.If there’s one loop that runs N times, it’s
O(n)
, and if you have a nested loop, it’s likelyO(n^2)
.You throw out any constant-time portion, so your function’s actual runtime might be the polynomial:
5n^3 + 2n^2 + 6n + 20
. But the big-O notation would simply beO(n^3)
in that case.I’m simplifying a little, but that’s the overview. I think a lot of people just memorize that certain algorithms have a certain complexity, like binary search being
O(log n)
for example.