爲什麼不是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 =數字

號因爲我們有一點複雜程度處理使每一個除了會採取O（n）和每個遞歸調用有一個至少一個除導致總的（正2000）* N。我在這裏做錯了什麼？

代碼從 - http://introcs.cs.princeton.edu/java/99crypto/Karatsuba.java.html

Answer 1

因爲只有3遞歸調用，而不是4 See slide 5

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