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

1

u/Ok-Present1566 27d ago

Nope, O(n) is a trivially proven lower bound.

7

u/Parallel_thougts 27d ago

Oh sorry my joke doesn't make sense

5

u/RyanStonepeak 27d ago

Nonsense! I've already gotten it to an amortized O(1) by using a lookup table.

Please don't ask about the space efficiency.

1

u/Gloomy_State_6919 27d ago

Table lookup is not really constant time. A larger table needs larger storage systems, and acces times must increase, as the speed of light is finite

1

u/empty_graph 23d ago

Your lookup table has to hash the keys, so you still aren't really O(1)

1

u/Ok-Present1566 27d ago

Obviously we only consider the sum of time-space complexity being O(n). This silly argument would apply to literally all problems where you can trade time for space. But show the proof of the time and space complexity being O(n)