My apologies if the question sounds naive, but I am trying to understand the idea of the complexity of time.

In general, it is said that the multiplication of Karatsuba has a temporal complexity of `O(n^1.5...)`

.

The algorithm assumes that addition and subtraction take approximately `O(1)`

every. However, for binary addition and subtraction, I don't think it is `O(1)`

. If I'm not mistaken, a typical addition or subtraction of two binary numbers takes `O(n)`

hour.

What will be the total time complexity of the next program that multiplies two binary numbers using **Karatsuba Something** which 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;
}
```