can anyone help me solve this problem?

CodePudding user response：

Let's have a look. Having a method (let it be C, C , C#, Java)

int Mult(int y, int z) {
  if (z == 0)
    return 0;
  else if (z % 2 != 0)
    return Mult(2 * y, z / 2)   y; // Note z / 2
  else
    return Mult(2 * y, z / 2);     // Note z / 2
}

we can see that on each recursive call we divide z by 2, e.g.

 Mult(7, 10) ==
 Mult(14, 5) == 
 Mult(28, 2)   14 == 
 Mult(56, 1)   14   56 == 
 Mult(112, 0)   14   56 == 
 
 0   14   56 == 70 # multipliction indeed: 7 * 10 == 70

Note how z changes: 10 -> 5 -> 2 -> 1 -> 0, so the number of recursive call is log(z) and we have O(log(z)) time complexity.

You can get rid of recursion and have an equivalent for loop

int Mult(int y, int z) {
  int result = 0;

  for (; z > 0; z /= 2, y = 2 * y)
    if (z % 2 != 0)
      result  = y;

  return result;
}

where O(log(z)) time complexity is more clearly seen: for (; z > 0; z /= 2...) {...}

CodePudding user response：

Every call to the function performs a test for zero. If the test is negative, then a recursive call is made with one doubling, one halving and possibly one addition, depending on the parity of the value of the argument z. So assuming that the initial z has N significant bits of which N1 ones, the total arithmetic count is

• N 1 tests for zero,
• N parity tests,
• N doublings,
• N halvings,
• N1 additions.

In terms of asymptotic complexity, this is Θ(log z).