To give background, there's two ways to multiply two complex numbers:
- Method A: requires 3 multiplications and 5 additions
- Method B: requires 4 multiplications and 2 additions
And it's given that multiplying two $m$ bit numbers is $O(m^2)$ and that adding two $m$ bit numbers is $O(m)$.
Now given a list of complex numbers, we can multiply them together using a divide and conquer algorithm that looks like this:
function divideAndConquer(list, i, j) {
if (i === j) {
return list[i]
}
const m = i + (j - i) / 2
return methodA(divideAndConquer(list, i, m), divideAndConquer(list, m + 1, j))
}
My goal is to find the complexity of the divide and conquer algorithm using methods A and B respectively. Using method A as an example, we could say that
- List of size 1: $T(1) = 1$
- List of size 2: $T(2) = 3am^2 + 5bm$ where $a > 0, b > 0$
because with one number you don't do anything, and with two numbers you do 3 multiplications and 5 additions.
However, now my issue is that I'm not quite sure that for $T(n)$ what I have is right because while it's quite obvious that it'll be something like
$$T(n) = T\left(\frac{n}{2}\right) + f(n)$$
I'm not really sure how to find out what $f(n)$ is because at each level $n$, $m$ will grow as a result of multiplication, meaning that $f(n) = 3am^2 + 5bm$ isn't accurate.
Essentially, the thing that confuses me is that there are two variables in play. The size of the list, $n$, and the size of the numbers in bits, $m$, that you're multiplying. So the heart of my question is really how do I solve a recurrence that has multiple variables? In this case $n$, and $m$.