Can anyone help me?
This is from my abstract algebra/Number theory book.
Show that given integers $n_1,n_2.......,n_k $ with each $n_i > 1$, we can compute the product $n := n_1 *n_2*........n_k$ in time $O(len(n)^2)$.
I know $len(n) \leq len(n_1)+.....+len(n_k)$
Hence, I was thinking worst run time would be $O(len(n_1)*len(n_2)*.....*len(n_5))$ $\quad$ #just guessing here.
Any hint:
Thanks
Consider an inductive argument.
For the base case, consider just $n_1$ and $n_2$. For the product $n = n_1 \cdot n_2$, the time complexity for the multiplication is, $$len(n_1)\cdot len(n_2) \leq len(n) \cdot len(n) = len(n)^2$$
so it is $O(len(n)^2)$.
Now suppose that $n = n_1 \cdot \dots \cdot n_k$ has complexity $O(len(n)^2)$. We will show that the time complexity of $n' = n_1 \cdot \dots \cdot n_{k+1}$ is $O(len(n')^2)$. Notice first we can do the first $k$ multiplications in $O(len(n)^2)$. Now we multiply $n$ and $n_{k+1}$ to obtain $n'$ which can be done in, $$len(n)\cdot len(n_{k+1}) \leq len(n') \cdot len(n') = len(n')^2.$$ So combined, the multiplications can be done in $$len(n)^2+len(n')^2 \leq len(n')^2+ len(n')^2 = 2len(n')^2$$ which is $O(len(n')^2)$.