> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/ecs122a-algorithm-design-lecture-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/ecs122a-algorithm-design-lecture-notes/divide_and_conquer/integer_multiplication.md).

# 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. 
* 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.