News for hackers. Stuff that matters.

A comment on Matrix multiplication inches closer to mythic goal. Parent comment

Re:Matrix multiplication inches closer to mythic goal by kripke on Wednesday March 24, 2021 @09:47AM (#26567108)
The choice of A_i now depends on n. The complexity of your construction is O(n^{2 + 1/argmax_i { N_i <= n}), not O(n^2).
[ Parent | on HN ]
Re:Matrix multiplication inches closer to mythic goal by woopwoop on Wednesday March 24, 2021 @01:43PM (#26570540)
Oh I wasn't claiming it's O(n), just O(n^{1+epsilon}) for any epsilon > 0. Indeed, the function inside your O is dominated by n^{2 + epsilon} for any epsilon > 0.
[ Parent | on HN ]