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

Answer 1

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