'Schoolbook' multiplication takes [itex]O(n^2)[/itex] operations. Karatsuba multiplication takes [itex]O(n^{\lg 3})\approx O(n^{1.59})[/itex] operations. The best method I know of (which is only practical for very large numbers) is [itex]O(n \log n \log\log n)[/itex].(adsbygoogle = window.adsbygoogle || []).push({});

Is there a known nontrivial lower bound on the complexity of multiplication? I read a paper that discussed the time-(silicon) area tradeoff on multiplication, but I wasn't able to get a useful bound from that (caring only about the time and not knowing how to 'remove' the area):

The Area-Time Complexity of Binary Multiplication

Can anyone help me out here?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Computational complexity

**Physics Forums | Science Articles, Homework Help, Discussion**