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 &gt; 0, b &gt; 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$.
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.