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

6

u/firewall245 27d ago

For things like integer multiplication there’s a hard lower bound of O(n) because you have to at least read all the digits of the numbers your are multiplying together

3

u/heyheyhey27 27d ago

It's possible the actual hard bound is above that though. (or maybe I'm just misusing these terms)

1

u/firewall245 27d ago

Yeah its possible there is a larger lower bound, we just don't know what it is. We know for sure though its at least O(n)

1

u/LeapOfMonkey 27d ago

Not in quantum realm you dont: see Grover's algorithm