Why isn't the complexity of karatsuba O(n^2)?

Question

import java.math.BigInteger;
import java.util.Random;

class Karatsuba {
private final static BigInteger ZERO = new BigInteger("0");

public static BigInteger karatsuba(BigInteger x, BigInteger y) {

    // cutoff to brute force
    int N = Math.max(x.bitLength(), y.bitLength());
    if (N <= 2000) return x.multiply(y);                // optimize this parameter

    // number of bits divided by 2, rounded up
    N = (N / 2) + (N % 2);

    // x = a + 2^N b,   y = c + 2^N d
    BigInteger b = x.shiftRight(N);
    BigInteger a = x.subtract(b.shiftLeft(N));
    BigInteger d = y.shiftRight(N);
    BigInteger c = y.subtract(d.shiftLeft(N));

    // compute sub-expressions
    BigInteger ac    = karatsuba(a, c);
    BigInteger bd    = karatsuba(b, d);
    BigInteger abcd  = karatsuba(a.add(b), c.add(d));

    return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(N)).add(bd.shiftLeft(2*N));
}


public static void main(String[] args) {
    long start, stop, elapsed;
    Random random = new Random();
    int N = Integer.parseInt(args[0]);
    BigInteger a = new BigInteger(N, random);
    BigInteger b = new BigInteger(N, random);

    start = System.currentTimeMillis(); 
    BigInteger c = karatsuba(a, b);
    stop = System.currentTimeMillis();
    StdOut.println(stop - start);

    start = System.currentTimeMillis(); 
    BigInteger d = a.multiply(b);
    stop = System.currentTimeMillis();
    StdOut.println(stop - start);

    StdOut.println((c.equals(d)));
}
}

n=number of digits

Since we are dealing with bit level complexity so every single addition would take O(n) and for each recursive call there is one at least one addition leading to a total of (n-2000)*n. What am I doing wrong here?

Code from-http://introcs.cs.princeton.edu/java/99crypto/Karatsuba.java.html

score 2 · Answer 1 · answered Dec 24 '16 at 14:18

2

Because there are only 3 recursive calls instead of 4. See slide 5

BigInteger ac    = karatsuba(a, c);
BigInteger bd    = karatsuba(b, d);
BigInteger abcd  = karatsuba(a.add(b), c.add(d));

answered Dec 24 '16 at 14:18

Pratik Deoghare

35,497
30
100
146

Still not getting it. (1+2)*(3+4)-a2-b2. In this equation (1+2) takes 1 step, so does 3+4 and so do the subtractions "-a2-b2" and so does the multiplication. Then the return step again requires 2 additions and 3 multiplications. I am having a tough time understanding how that doesn't exceed n^2. Can you please further clarify this? – Ambikeya Singh Sangwan Dec 26 '16 at 03:18
1

We are dealing with large numbers here. Additions and multiplications cost is different. We know that addition of large numbers is O(n). So 2 additions will cost O(n). What is the complexity of multiplication? Well, its the complexity of above algorithm since its _the multiplication algorithm_ that we are using. So we calculate that with recurrence T(n) = 3T(n/2) + O(n) = 3 multiplications of 1/2 size numbers + few additions. Does that make sense? – Pratik Deoghare Dec 26 '16 at 17:56

Why isn't the complexity of karatsuba O(n^2)?

1 Answers1