1
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.