1

In Java, there is the BigInteger class, which seems to be holding its contents internally as an array of ints. I'm imagining that additions/subtraction/bitShifting of two BigInteger numbers are O(N) "linear operations" as such. In fact, it seems that even multiplication and division are O(N log N)?

Without understanding the special large-number algorithms, would this be a sufficiently accurate general answer?

David T.
  • 22,301
  • 23
  • 71
  • 123
  • 1
    https://stackoverflow.com/questions/2154117/what-complexity-are-operations-on-java-7s-biginteger – xingbin Sep 11 '20 at 07:13
  • Note that N would usually denote the actual number stored in the BigInt, not its size in memory, which is denoted n = O(log N). All BigInt operations should at least be polynomial in n i.e. polylogarithmic in N. – Gerhood Sep 11 '20 at 07:29
  • The implementation in the BigInteger class has been gradually getting more sophisticated over the years, but for operands less than about 2500 bits an O(N\*\*2) algorithm is used. Operands larger than that are multiplied using the Karatsuba algorithm which is an O(N\*\*1.58) algorithm. Still more sophisticated algorithms are used as the operands get really large. – President James K. Polk Sep 11 '20 at 22:04

0 Answers0