Assume fast multiplication: given two integers u and v, one can compute
the product uv in essentially linear time, i.e., time at most n^{1+o(1)}
where n is the total number of input bits.
Here is a recursive algorithm that, given integers u[1],u[2],...,u[k],
computes the product of all the integers: if k = 1, return u[1];
otherwise recursively multiply u[1],u[2],...,u[floor(k/2)], recursively
multiply u[floor(k/2)+1],...,u[k], and return the product of these two
results.
Prove that this algorithm takes time at most n^{1+o(1)} where n is the
total number of input bits.