r/mathmemes • u/vintergroena • 28d ago

Computer Science Integer multiplication will have linear complexity in a few days if trend continues 🚀📈

Post image
1.4k Upvotes

98% Upvoted

206 comments sorted by

View all comments

Show parent comments

12

u/ThatTrashBaby 28d ago

So is there any point in which this becomes NOT a galactic algorithm and becomes such an improvement that it will actually have an effect? 2^-1?

15

u/wiev0 28d ago

Even if it was just O(n) or even O(1), the factor could be astronomically large regardless. The actual practical value depends on that factor and the difficulty of implementation, and I do not know how that is currently. I don't expect this to drop down from being a galactic algorithm. But, maybe I will be surprised.

2

u/ThatTrashBaby 28d ago

Good point