3
$\begingroup$

Show that we can compute the product $n = \Pi_i\ n_i$ in time $O(len(n)^2)$ for given integers $n_1,...n_k$ with each $n_i> 1$.
I know that we can compute $ab$ in time $O(len(a)len(b))$ courtesy the basic multiplication algorithm. But this result gives the running time for computing the product n as $O(\Pi_i\ len(n_i))$. So where does $len(n)$ come into picture unless question indicates the use of another algorithm?

One way I can look into this is as follows: let $i = 2$ so that $n = ab$. We can compute $n = ab$ in $O(len(a)len(b))$. Also $len(\Pi_{i=1}^k\ n_i) \leq \sum_{i=1}^k\ len(n_i)$(proved in a previous exercise) so for i = 2: $len(n) \leq len(a)+len(b)$ where $n = ab$.
Let $len(a) = l_a$ and $len(b) =l_b$. So we can compute $n = ab$ in $O(l_al_b)$. Now $(l_a + l_b)^2 \geq 4l_al_b \implies(l_a + l_b)^2 > l_al_b \implies\ O(l_al_b) \cong O((l_a+l_b)^2) \cong\ O(len(n)^2)$. We can now extend this proof for $i =1$ to $i = k$ by induction. But this logic seems crude to me at its best. Is this approach correct?

  • 1
    Your approach looks OK to me.2012-09-05

1 Answers 1

1

Let $N_i = \prod_{j=1}^i n_i$. You can compute $N_{j+1}$ from $N_j$ by the equation $N_{j+1} = N_j n_{j+1}$, costing $O(len(N_j)len(n_{j+1}))$ time. The total time to compute $N_i$ starting from $N_0 = 1$ is $\sum_{j=0}^{i-1} O(len(N_j)len(n_{j+1}))$. Since $N_j \le N_i$, we get $O(len(N_i)\sum_{j=1}^{i} len(n_j)) = O(len(N_i)^2)$.

Note that I used the fact that $O(\sum_{j=1}^i len(n_j)) = O(len(N_i) + i)$ and, when all $n_j > 1$, $i = O(len(N_i))$ because $N_i \ge 2^i$.

  • 0
    thanks for your explanation.2012-09-06