You must log in or register to comment.
There’s O(1), O(n), O(nlgn), O( this code is crap ).
[Cries in matrix multiplication]
Matrix multiplication is O(n) if you do it in parallel /j
Umm, AKCTSHUALLY it gets more like O(n2) in parallel, assuming you’re using a physically achievable memory. There’s just a lot of criss-crossing the entries have to do.
Strassen’s algorithm gets O(n2.8) in serial by being terrible, and the weird experimental ones get O(n2.3), but the asymptotic benefits only kick in if you’re a Kardashev III civilisation computing a single big product on a Dyson sphere.
I can’t decide whether this sentence is a joke or not. It has the same tone that triggers my PTSD from my CS degree classes and I also do recognize some of the terms, but it also sounds like it’s just throwing random science terms around as if you asked a LLM to talk about math.
I love it.
Also, it’s apparently also real and correct.
Yeah, in fact, I somehow calculated in assumption of
nbeing the amount of elements in matrix, notn²(assuming square matrix)But I am impressed to know that there are serial algorithms that approach
O(n²), thank you for sharing that infoYeah, they work by turning the problem into some crazy kind of group theory and attacking it that way. Every once in a while someone shaves the decimal down slightly, just by implementing the deep math in a more efficient way. A new approach will be needed if it is in fact possible to get down to O(n2), though. Strassen’s is a divide and conquer algorithm, and each step of the iteration looks like this:
S[1] = B[1, 2] - B[2, 2] S[2] = A[1, 1] + A[1, 2] S[3] = A[2, 1] + A[2, 2] S[4] = B[2, 1] - B[1, 1] S[5] = A[1, 1] + A[2, 2] S[6] = B[1, 1] + B[2, 2] S[7] = A[1, 2] - A[2, 2] S[8] = B[2, 1] + B[2, 2] S[9] = A[1, 1] - A[2, 1] S[10] = B[1, 1] + B[1, 2] P[1] = STRASSEN(A[1, 1], S[1]) P[2] = STRASSEN(S[2], B[2, 2]) P[3] = STRASSEN(S[3], B[1, 1]) P[4] = STRASSEN(A[2, 2], S[4]) P[5] = STRASSEN(S[5], S[6]) P[6] = STRASSEN(S[7], S[8]) P[7] = STRASSEN(S[9], S[10]) C[1..n / 2][1..n / 2] = P[5] + P[4] - P[2] + P[6] C[1..n / 2][n / 2 + 1..n] = P[1] + P[2] C[n / 2 + 1..n][1..n / 2] = P[3] + P[4] C[n / 2 + 1..n][n / 2 + 1..n] = P[5] + P[1] - P[3] - P[7] return CIn my copy of Introduction to Algorithms, it says something like “this is the most bullshit algorithm in the book and it’s not close” underneath. You can make it a bit neater by representing the multiplication operation as a 3-dimensional tensor, but at the end of the day it’s still just a stupid arithmetic trick. One that’s built into your GPU.
Why would you want a specific time complexity? Wouldn’t it be better if it’s faster?
Likely they want a lower time complexity.
for example a question can be trivially solved in O(n^2). but there is no know < O(n) solution, so they ask for O(n)
Most of the time O(n^2) is optimized to O(n log n). You’ll get some sort of award if you can figure out a sorting function that runs in O(n).
O(n)? More LikeOh(No)Just add a delay that pads it out the execute time to 10 seconds. O(1) ez.
Great, now I’m hungry for apples.
O(n!). I like it.
O((2(n2))!) or bust.
O(BB(n))
“That matches no single computable function” is just an excuse.
That’s still good! I’m proud of you for working though the parts of the problem that you were capable of
