title: What is the time complexity of calculating factorial n! using Java's BigInteger
body: <p>Suppose the algorithm is as below:</p>
  
  <pre><code>public static BigInteger getFactorial(int num) {
      BigInteger fact = BigInteger.valueOf(1);
      for (int i = 1; i &lt;= num; i++)
          fact = fact.multiply(BigInteger.valueOf(i)); // ? time complexity
      return fact;
  }
  </code></pre>
  
  <p>It seems hard to calculate number of digits of <strong>fact</strong>.</p>
  
  <p>Optimized version:</p>
  
  <pre><code>    public BigInteger getFactorial2(long n) {
          return subFactorial(1, n);
      }
      private BigInteger subFactorial(long a, long b) {
          if ((b - a) &lt; 10) {
              BigInteger res = BigInteger.ONE;
              for (long i = a; i &lt;= b; i++) {
                  res = res.multiply(BigInteger.valueOf(i));
              }
              return res;
          } else {
              long mid = a + (b - a) / 2;
              return subFactorial(a, mid).multiply(subFactorial(mid + 1, b));
          }
      }
  </code></pre>