quiz is the second one. Namely, the only thing that changes with respect to the

first recurrence, is that the number of recursive calls drops from four down to

three. A coupla quick comments. So, first of all, I'm being a little bit sloppy when

I say there's three recursive calls, each on digits, each on numbers with n over two

digits. When you take the sums a plus b and c plus d, those might well have n over

two plus one digits. Amongst friends, let's ignore that, let's just call it n

over two digits and each did recursive calls. As usual, the extra plus one is not

gonna matter in the final analysis. Secondly, I'm ignoring exactly. What the

constant factor is in the linear work done outside of the recursive calls. Indeed,

it's a little bit bigger in Gaus's algorithm than it is in the naive

algorithm with four recursive calls. But it's only a constant factor and that's

gonna be supressed in the big O notation. So let's look at this occurance and

compare it to two other recurrences, one bigger, one smaller. So first of all, as

we noted, it differs from the previous recurrence of the naive recursive

algorithm in having one fewer recursive calls. So we have no idea what the running

time is of either of these two recursive algorithms but we should be confident that

this one's. Certainly can only be better, that's for sure. Another point of contrast

is Merge Short. So think about what the recurrence would look like for the Merge

Short algorithm. It would be almost identical to this one, except instead of a

three, we'd have a two, right? Merge Short makes two recursive calls, each on an

array of half the size. And outside of the recursive calls, it does linear work,

mainly for the merged subroutine. We know the running time of Merge Short. It's N

log n. So this algorithm, Gaus's algorithm is gonna be worse, but we don't

know by how much. So while we have a couple clues about what the running time

of this algorithm might be more or less than, honestly, we have no idea what the

running time of Gaus's recursive algorithm for integer multiplication

really is. It is not obvious, we currently have no intuition for it. We don't know

what the solution to this recurrence is. But it will be one super special case of

the general master method, which we'll tackle next.