# Integer Multiplication

### Input

* Two n digit numbers x and y.

### Output

* $$x \* y$$;product.

## Algorithm Space

* In grade school we've been taught well defined set of rules to follow for integer multiplication.&#x20;
* Time complexity analysis of grade-school algorithm:
  * Given number A with n digits, and number B with y digits, for each number in y, we multiply with n. Then we add the numbers together.
  * This gives us a total of $$O(|A| \* |B| + c)$$
  * Or $$O(n^2)$$

## Karatsubu Multiplication

* Algorithm is not exactly intuitive so I wont go through it.
* But the main idea is that the algorithm space is large, and there are different design methods to solve a problem.
* Can be optimized to remove one recursive call, and increase its running time performance.
