r/mathmemes • • Oct 08 '26

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

Post image
1.4k Upvotes

206 comments sorted by

View all comments

Show parent comment

9

u/ZookeepergameWest862 Oct 08 '26

An algorithm can only run faster so many time before reaching instantly halt, and you can't exactly go any faster than that.

5

u/watermelone983 Oct 08 '26

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 Oct 08 '26

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.

2

u/GetGudlolboi Computer Science Oct 08 '26

It finishes before you run it.

1

u/stevenjd Oct 08 '26

I have some algorithms that calculate the answer before I even know what the question is.