Description
Author of the first fast computational method, Karatsuba was a Russian mathematician best known for discovering the first multiplication algorithm that runs in less than O(n²) time—specifically his algorithm is O(n log2 3) or about O(n 1.58). Karatsuba also wrote papers on such diverse areas as finite automata theory and the Riemann Zeta function.
He enjoyed mountaineering and served as head of the Laboratory of Analytic Number Theory at the Steklov Mathematical Institute in Moscow.
