@pervognsen I've always thought it was weird to call matrix multiplication's "n" the _dimension_ of the matrix...
-
-
Replying to @cmuratori
@cmuratori@pervognsen ... because that's not the size of the "input", in a sense - it's the sqrt of the size of the input, etc.1 reply 0 retweets 0 likes -
Replying to @cmuratori
@cmuratori Now you'd have to say the naive algorithm takes O(n^(3/2)) time!2 replies 0 retweets 0 likes -
Replying to @pervognsen
@cmuratori In square matrix multiplication, there are n^2 entries and each is a dot product of n-vectors.2 replies 0 retweets 0 likes -
Replying to @pervognsen
@pervognsen That is always how I think of it, so I don't think of it as O(n^3), I think of it as O(n root n), so to speak :)1 reply 0 retweets 0 likes -
Replying to @cmuratori
@cmuratori@pervognsen I feel like I'm in the right on this one, though :P2 replies 0 retweets 0 likes -
Replying to @cmuratori
@cmuratori Because it's _not_ n^3 in the input, so you wouldn't expect it to "scale as the cube" of, you know, the data transfer time!1 reply 0 retweets 0 likes -
Replying to @cmuratori
@cmuratori Which is what you would _normally_ think of n^3 as meaning.1 reply 0 retweets 0 likes -
Replying to @cmuratori
@cmuratori It's like, "how long does it take to copy this block of memory?" "It's O(n)!" "Oh, but it's a matrix." "In that case, O(n^2)!"1 reply 0 retweets 2 likes
@cmuratori I kid, of course, but still it seems like it violates the principle of least surprise :)
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.