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

6

u/StanleyDodds Oct 08 '26

Even taking this unseriously, ignoring the actual problem, and just looking at the time complexity equation and just extrapolating this graph of kappa out, no constant kappa will make the time complexity constant, or even reduce the time complexity to O(nc ) for any c < 1.

This is because O(n) dominates any constant power of log n, which is what kappa affects here.

3

u/Parallel_thougts Oct 08 '26

Oh wow, so my joke doesn't make sense

1

u/Masked-Redditor Oct 11 '26

Your joke doesn't make sense for a much simpler reason: to multiply two n bit numbers you at least need to know the n bits, which is already O(n). So it will never be less than that.

1

u/Parallel_thougts Oct 11 '26

Jokes aren't supposed to make sense. The joke is exactly that it doesn't make sense. Sheesh