What is the time complexity of a binary multiplication using Karatsuba Algorithm?

Question

My apologies if the question sounds naive, but I'm trying wrap my head around the idea of time complexity.

In general, the Karatsuba Multiplication is said to have a time complexity of O(n^1.5...). The algorithm assumes that the addition and subtraction take about O(1) each. However, for binary addition and subtraction, I don't think it will be O(1). If I'm not mistaken, a typical addition or subtraction of two binary numbers takes O(n) time.

What will be the total time complexity of the following program then that multiplies two binary numbers using Karatsuba Algo that in turn performs binary addition and subtraction?

long multKaratsuba(long num1, long num2) {
 if ((num1>=0 && num1<=1) && (num2>=0 && num2<=1)) {
   return num1*num2;
 }

 int length1 = String.valueOf(num1).length(); //takes O(n)? Not sure
 int length2 = String.valueOf(num2).length(); //takes O(n)? Not sure

 int max = length1 > length2 ? length1 : length2;
 int halfMax = max/2;

 // x = xHigh + xLow
 long num1High = findHigh(num1, halfMax); // takes O(1)
 long num1Low = findLow(num1, halfMax); // takes O(1)

 // y = yHigh + yLow 
 long num2High = findHigh(num2, halfMax); // takes O(1)
 long num2Low = findLow(num2, halfMax); // takes O(1)

 // a = (xHigh*yHigh)
 long a = multKaratsuba(num1High, num2High);

 // b = (xLow*yLow)
 long b = multKaratsuba(num1Low, num2Low);

 //c = (xHigh + xLow)*(yHigh + yLow) - (a + b);
 long cX = add(xHigh,xLow); // this ideally takes O(n) time
 long cY = add(yHigh,yLow); // this ideally takes O(n) time
 long cXY = multKaratsuba(cX, cY);
 long cAB = add(a, b) // this ideally takes O(n) time
 long c = subtract(cXY, cAB) // this ideally takes O(n) time

 // res = a*(10^(2*m)) + c*(10^m) + b
 long resA = a * (long) Math.pow(10, (2*halfMax)); // takes O(1)
 long resC = c * (long) Math.pow(10, halfMax); // takes O(1)
 long resAC = add(resA, resC); // takes O(n)
 long res = add(resAC, b); // takes O(n)

 return res;
}

Answer 1

You're mistaken. The analysis of the Karatsuba algorithm takes addition and subtraction into account.

If you analyze your pseudo-code, you can see that you have exactly 3 recursive function calls with arguments of size $n/2$, and all other operations like addition, subtraction, extracting the higher and lower bits, ..., run in $O(n)$.

Therefore you get the recursion $T(n) = 3 \cdot T(n/2) + O(n)$ for the complexity, which gives the following according to the Master theorem: $$T(n) = \Theta(n^{\log_2 3}) = \Theta(n^{1.58...})$$

---

Fun fact: even if you assume that all the bitwise operations (addition, subtraction, ...) take $O(1)$, the code will still have the same complexity. Since the number of calls to the three subproblems dominates the other work. But I doubt, that any book/lecturer would assume that the bitwise operations are constant, since the whole point of the algorithm is that you want to multiply large numbers.

---

Btw, you have some small errors in your pseudo-code/analyze. E.g. here:

long resA = a * (long) Math.pow(10, (2*halfMax)); // takes O(1)

You want to multiply with a power of 2, to make it efficient (since you are working with binary numbers). And even corrected it will not run in $O(1)$, because you need to copy/move $O(n)$ bits. So this line will also run in $O(n)$.