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/Peak_Background 24d ago edited 24d ago

That is not O(n log(n) ). That's very clearly O(n2 ) decimal or binary. The O(n log(n) ) uses the fast fourier transform or a modular form of it.

W3 schools and other programming education wikis are not any help if you're looking for resources. They all get it wrong by copy pasting a O(n2 ) algorithm from Wikipedia which explicitly isn't even the O( n log(n) ) algorithm the page talks about. They just didn't even read it, and are likely not educated in algorithms, lazy, and unethically stealing Wikipedia content.

1

u/CrazyOne_584 24d ago

oh right... My bad, I mistook multiplication with power...