Search code examples
javaalgorithmasymptotic-complexity

What is asymptotic complexity of Integer's multiplication in Java

I am interested in asymptotic complexities of multiplication operations for int type, Integer and BigInteger objects:

int i,j = <value>;
i * j; // O?
Integer i,j = new Integer(<value>);  
i * j; // O?
BigInteger i,j = new BigInteger(<value>);
i.multiply(j); //O?
Solution

  • BigInteger.multiply uses multiple algorithms, depending on the size of the number.

    Small numbers use naive algorithm O(n^2)

    Larger numbers use Karatsuba algorithm O(n^1.585)

    Largest numbers use Toom–Cook algorithm O(n^1.465)

    I could not easily determine the threshold of the length of the number used to determine which algorithm to use. Please edit my answer if you know this.

    int multiplication is O(1) because the size of the integer (n) is a constant value