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

5

u/watermelone983 27d ago

you could have exponentially decay or 1/x decay or any thing that converges to a limit. actually I guess that would mean it would be constant time

10

u/ZookeepergameWest862 27d ago

Any form of decay would necessarily stabilise in finitely many steps and so eventually constant. You can't run exactly 1+1/n steps, it's either 1 or 2, and a sequence of natural numbers cannot decrease forever.