# Complexity analysis of recurrence with multiple variables

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

• "which basically tells us that multiplication is more expensive than addition" -- not if you only have $O$, it doesn't. – Raphael Oct 25 '17 at 9:31
• "However, it seems like I'm on the wrong track according to someone else." -- what are they saying? – Raphael Oct 25 '17 at 9:34
• @Raphael regarding being on the wrong track, I was told that the master theorem wouldn't help. – john Oct 25 '17 at 16:47
• The recurrence you give for $T$ can be solved with the Master theorem, but it may be the wrong recurrence. – Raphael Oct 25 '17 at 21:38

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