Complexity analysis of recurrence with multiple variables

Question

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$.

Answer 1

Since you know only $O$-bounds for the basic operations, you can not derive more precise bounds for $f$, nor $T$. Furthermore, if you had exact cost functions for the basic operations, solving divide-and-conquer recurrences exactly is very hard.

So, what the exercise authors probably want you to do is to say,

• $f \in \Theta(m^2)$ (assuming that the bound for multiplication is tight, which they probably wanted to imply but didn't express properly) in either case, and
• solve the schematic recurrence using the Master theorem (e.g. by substituting $f(m)$ with $m^2$).

You'll get out the correct $\Theta$ bound that way.