What complexity are operations on BigInteger?
biginteger, complexity-theory, java
Solution
If you look at the code for `BigInteger` (provided with JDK), it appears to me that `multiply(..)` has O(n^2) (actually the method is `multiplyToLen(..)`). The code for the other methods is a bit more complex, but you can see yourself.
Note: this is for Java 6. I assume it won't differ in Java 7.
Problem
What complexity are the methods `multiply`, `divide` and `pow` in `BigInteger` currently? There is no mention of the computational complexity in the documentation (nor anywhere else).