There have been multiple accounts created with the sole purpose of posting advertisement posts or replies containing unsolicited advertising.

Accounts which solely post advertisements, or persistently post them may be terminated.

joyjoy ,

O(n!). I like it.

palordrolap ,

O((2^(n^2))!) or bust.

CanadaPlus , (edited )

O(BB(n))

“That matches no single computable function” is just an excuse.

BleatingZombie ,

That’s still good! I’m proud of you for working though the parts of the problem that you were capable of

MajorHavoc ,

There’s O(1), O(n), O(nlgn), O( this code is crap ).

CanadaPlus ,

[Cries in matrix multiplication]

sukhmel ,

Matrix multiplication is O(n) if you do it in parallel /j

CanadaPlus , (edited )

Umm, AKCTSHUALLY it gets more like O(n^2^) 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(n^2.8^) in serial by being terrible, and the weird experimental ones get O(n^2.3^), but the asymptotic benefits of Coppersmith-Winograd and friends only kick in if you’re a Kardashev III civilisation computing a single big product on a Dyson sphere.

sukhmel ,

Yeah, in fact, I somehow calculated in assumption of n being the amount of elements in matrix, not n² (assuming square matrix)

But I am impressed to know that there are serial algorithms that approach O(n²), thank you for sharing that info

CanadaPlus , (edited )

Yeah, 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(n^2^), though. Strassen’s is a divide and conquer algorithm, and each step of the iteration looks like this:


<span style="color:#323232;">    S[1] = B[1, 2] - B[2, 2]
</span><span style="color:#323232;">    S[2] = A[1, 1] + A[1, 2]
</span><span style="color:#323232;">    S[3] = A[2, 1] + A[2, 2]
</span><span style="color:#323232;">    S[4] = B[2, 1] - B[1, 1]
</span><span style="color:#323232;">    S[5] = A[1, 1] + A[2, 2]
</span><span style="color:#323232;">    S[6] = B[1, 1] + B[2, 2]
</span><span style="color:#323232;">    S[7] = A[1, 2] - A[2, 2]
</span><span style="color:#323232;">    S[8] = B[2, 1] + B[2, 2]
</span><span style="color:#323232;">    S[9] = A[1, 1] - A[2, 1]
</span><span style="color:#323232;">    S[10] = B[1, 1] + B[1, 2]
</span><span style="color:#323232;">    P[1] = STRASSEN(A[1, 1], S[1])
</span><span style="color:#323232;">    P[2] = STRASSEN(S[2], B[2, 2])
</span><span style="color:#323232;">    P[3] = STRASSEN(S[3], B[1, 1])
</span><span style="color:#323232;">    P[4] = STRASSEN(A[2, 2], S[4])
</span><span style="color:#323232;">    P[5] = STRASSEN(S[5], S[6])
</span><span style="color:#323232;">    P[6] = STRASSEN(S[7], S[8])
</span><span style="color:#323232;">    P[7] = STRASSEN(S[9], S[10])
</span><span style="color:#323232;">    C[1..n / 2][1..n / 2] = P[5] + P[4] - P[2] + P[6]
</span><span style="color:#323232;">    C[1..n / 2][n / 2 + 1..n] = P[1] + P[2]
</span><span style="color:#323232;">    C[n / 2 + 1..n][1..n / 2] = P[3] + P[4]
</span><span style="color:#323232;">    C[n / 2 + 1..n][n / 2 + 1..n] = P[5] + P[1] - P[3] - P[7]
</span><span style="color:#323232;">    return C
</span>

In 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.

Mikina ,

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.

CanadaPlus ,

Thank you, I’m glad to share the pain of numerical linear algebra with anyone who will listen.

RonSijm ,
@RonSijm@programming.dev avatar

O(n)? More Like Oh(No)

Venator , (edited )

Why would you want a specific time complexity? Wouldn’t it be better if it’s faster? /s

JaddedFauceet ,

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)

sukhmel ,

That’s a huge leap from O(n²) to O(n), in this example it would likely good to at least specify that it should be strictly less than best known solution (not sure if there are such cases on leet code, I thought they only restrict you to what is known to be solvable)

tiefling ,

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).

bradorsomething ,

Great, now I’m hungry for apples.

nothacking ,

Just add a delay that pads it out the execute time to 10 seconds. O(1) ez.

  • All
  • Subscribed
  • Moderated
  • Favorites
  • •
  • [email protected]
  • random
  • lifeLocal
  • goranko
  • All magazines
    •