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.