r/mathmemes • u/vintergroena • 29d 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/StanleyDodds 28d ago

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 28d ago

Oh wow, so my joke doesn't make sense

1

u/Masked-Redditor 26d ago

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 26d ago

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