“Since antiquity, #mathematicians have suspected that O(n2) was an inherent speed limit for #multiplication. The celebrated Soviet math professor #AndreyKolmogorov posed the O(n^2) speed limit as a formal #conjecture and mentioned it during a 1960 seminar at Moscow State University. Whenever mathematicians propose a conjecture, they are planting a flag of sorts and waiting for others to either prove or disprove them. It took just a week for #AnatolyKaratsuba, then a 23-year-old student in the audience, to return and prove Kolmogorov wrong. Kolmogorov was stunned. The result was published in the prestigious Proceedings of the USSR Academy of Sciences, but amusingly, Karatsuba didn’t write it. Kolmogorov wrote the formal proof himself and submitted it for publication with Karatsuba listed as the lead author. Karatsuba only found out about the paper when he received the reprints in the mail.
Karatsuba’s genius was realizing that you can trade expensive, time-consuming multiplications for cheap, fast #additions. Adding two n-digit numbers takes only O(n) time because it entails a single sweep through the digits rather than a complete sweep through the top number for every digit of the bottom number, as in multiplication.”
#maths / #computation