The key here is that, we now just need to calculate D1 E1, D1 E0, D0 E1, and D0 E0.
Those are all polynomials of degree n over 2.
And so, now we can go ahead and use a recursive solution to solve this problem.
So it gives us a divide and conquer problem.
Its run time is T of n, equals 4 T of n over 2.
Why 4?
4, because we're breaking into 4 subproblems.
Each of them takes time T of n over 2
ecause the problem is broken in half.
Plus, then, in order to take the results and
do our addition that's going to take order n time.
So some constant k, times that.
Let's look at an example.
So we have, n is 4, so we have degree three polynomials.
And we're going to break up A of x into the top half, 4x plus 3,
and the bottom half, 2x plus 1.
Similarly, we're going to break up the top half of B of x.
X cubed plus 2 x squared just becomes x plus 2.
And 3x plus 4, stays at 3x plus 4.
Now, we compute D1 E1.
So multiplying together, 4x + 3, times x plus 2, gives us 4 x squared + 11x + 6.
Similarly, we calculate D1 E0, D0 E1, and D0 E0.
Now we've done all four of those computations, AB is just D1 E1,
4 x squared + 11x + 6 times x to the 4th, plus the sum of D1 E0 and
D0 E1, times x squared, plus finally D0 E0.
If we sum this all together, we get 4 x to the 6th, plus 11 x to the 5th,
plus 20 x to the 4th, plus 30 x cubed, plus 20 x squared, plus 11x plus 4.
Which is our solution.
Now, how long's this take to run?
We're going to look at that in a moment.
Let's look at the actual code for it.
So we're going to compute a resulting array, from 0 to 2n-2, so
is all the results coefficients.