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

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;
}


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

• Thanks for pointing out the errors. Explanation makes sense – Auro Aug 16 '19 at 22:15