# Karatsuba Algorithm ( Multiplication)

Jump to navigation
Jump to search

## Time Complexity

$O(n^{1.{5}8})$

## Space Complexity

$O(n)$ bits

(Re-use space across recursive subcalls (to obtain the recursion S(n) = S(n/2)+O(n)))

## Description

## Approximate?

Exact

## Randomized?

No, deterministic

## Model of Computation

Word RAM?

## Year

1962

## Reference

http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=26729&option_lang=eng