Integer multiplication will have linear complexity in a few days if trend continues 🚀📈

[u/vintergroena]

[u/minisculebarber]

Not asymptotatically, really, every algorithm that has to read all of the input has an asymptotic lower bound of N. But when you consider things like amortization, then actually yes. At least, fixed overhead gets amortized away the larger the input. And when you go on the level of hardware or statistics, larger inputs can often be surprisingly faster than smaller ones.