How to understand intuitively the fact that $\log(n!) = n\log(n) - n + O(\log(n))$?

Question

The error in the approximation for $\log(n!)$ by $n\log(n) - n$ is $O(\log(n))$. Doesn't this imply that as $n$ increases, the error increases, but very, very slowly (similar to $\log(n)$)? But doesn't this approximation improve as $n$ gets larger (in other words, the error should be decreasing!). It would also suggest that the error is lower for smaller $n$ since $\log(n)$ is monotonically increasing?

I am certainly making some conceptual errors in coming to this conclusion, can you correct them?

Answer 1

Technically a $O(log(n))$ is not something that has to increase with a speed comparable to $log(n)$, it is rather something that cannot increase faster than some fixed constant times $log(n)$.

Secondly, even if in this case the error does increase, the point is that relatively to your main terms $nlog(n)−n$, an error of $log(n)$ is small.

If you are trying to find approximately the age of the universe, an error of $10,000$ years is small.

Answer 2

Using natural log, $$ \log (n!) = n \log n - n + \frac{1}{2} \log (2 \pi n) + \log \left( 1 + \frac{1}{12n} + \frac{1}{288 n^2} + O \left( \frac{1}{n^3} \right) \right) $$

$$ \log (n!) = n \log n - n + \frac{1}{2} \log (2 \pi n) + \frac{1}{12n} - \frac{1}{360 n^3} + O \left( \frac{1}{n^5} \right) $$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

The computer output below illustrates the approximation $$ \log (n!) \approx n \log n - n + \frac{1}{2} \log (2 \pi n) $$

  1 log fac: 0 approx : -0.0810615  error : 0.0810615 1/ error : 12.3363
  2 log fac: 0.693147 approx : 0.651806  error : 0.0413407 1/ error : 24.1892
  3 log fac: 1.79176 approx : 1.76408  error : 0.0276779 1/ error : 36.1299
  4 log fac: 3.17805 approx : 3.15726  error : 0.0207907 1/ error : 48.0985
  5 log fac: 4.78749 approx : 4.77085  error : 0.0166447 1/ error : 60.0792
  6 log fac: 6.57925 approx : 6.56538  error : 0.0138761 1/ error : 72.0662
  7 log fac: 8.52516 approx : 8.51326  error : 0.0118967 1/ error : 84.0569
  8 log fac: 10.6046 approx : 10.5942  error : 0.0104113 1/ error : 96.0498
  9 log fac: 12.8018 approx : 12.7926  error : 0.00925546 1/ error : 108.044
 10 log fac: 15.1044 approx : 15.0961  error : 0.00833056 1/ error : 120.04
 11 log fac: 17.5023 approx : 17.4947  error : 0.00757368 1/ error : 132.036
 12 log fac: 19.9872 approx : 19.9803  error : 0.00694284 1/ error : 144.033
 13 log fac: 22.5522 approx : 22.5458  error : 0.00640899 1/ error : 156.031
 14 log fac: 25.1912 approx : 25.1853  error : 0.00595137 1/ error : 168.029
 15 log fac: 27.8993 approx : 27.8937  error : 0.00555473 1/ error : 180.027
 16 log fac: 30.6719 approx : 30.6667  error : 0.00520766 1/ error : 192.025
 17 log fac: 33.5051 approx : 33.5002  error : 0.0049014 1/ error : 204.024
 18 log fac: 36.3954 approx : 36.3908  error : 0.00462915 1/ error : 216.022
 19 log fac: 39.3399 approx : 39.3355  error : 0.00438556 1/ error : 228.021
 20 log fac: 42.3356 approx : 42.3315  error : 0.00416632 1/ error : 240.02
 21 log fac: 45.3801 approx : 45.3762  error : 0.00396795 1/ error : 252.019
 22 log fac: 48.4712 approx : 48.4674  error : 0.00378762 1/ error : 264.018
 23 log fac: 51.6067 approx : 51.6031  error : 0.00362296 1/ error : 276.017
 24 log fac: 54.7847 approx : 54.7813  error : 0.00347202 1/ error : 288.017
 25 log fac: 58.0036 approx : 58.0003  error : 0.00333316 1/ error : 300.016
 26 log fac: 61.2617 approx : 61.2585  error : 0.00320497 1/ error : 312.015
 27 log fac: 64.5575 approx : 64.5545  error : 0.00308628 1/ error : 324.015
 28 log fac: 67.8897 approx : 67.8868  error : 0.00297606 1/ error : 336.014
 29 log fac: 71.257 approx : 71.2542  error : 0.00287345 1/ error : 348.014
 30 log fac: 74.6582 approx : 74.6555  error : 0.00277767 1/ error : 360.013
 31 log fac: 78.0922 approx : 78.0895  error : 0.00268808 1/ error : 372.013
 32 log fac: 81.558 approx : 81.5554  error : 0.00260408 1/ error : 384.012
 33 log fac: 85.0545 approx : 85.0519  error : 0.00252518 1/ error : 396.012

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

The computer output below illustrates the better approximation $$ \log (n!) \approx n \log n - n + \frac{1}{2} \log (2 \pi n) + \frac{1}{12n} $$

  1 log fac: 0 approx : 0.00227187  error : -0.00227187 1/ error : -440.167
  2 log fac: 0.693147 approx : 0.693473  error : -0.000325971 1/ error : -3067.76
  3 log fac: 1.79176 approx : 1.79186  error : -9.98521e-05 1/ error : -10014.8
  4 log fac: 3.17805 approx : 3.1781  error : -4.26612e-05 1/ error : -23440.5
  5 log fac: 4.78749 approx : 4.78751  error : -2.19755e-05 1/ error : -45505.3
  6 log fac: 6.57925 approx : 6.57926  error : -1.27601e-05 1/ error : -78369.5
  7 log fac: 8.52516 approx : 8.52517  error : -8.05196e-06 1/ error : -124193
  8 log fac: 10.6046 approx : 10.6046  error : -5.4014e-06 1/ error : -185137
  9 log fac: 12.8018 approx : 12.8018  error : -3.79708e-06 1/ error : -263361
 10 log fac: 15.1044 approx : 15.1044  error : -2.7699e-06 1/ error : -361024
 11 log fac: 17.5023 approx : 17.5023  error : -2.08209e-06 1/ error : -480287
 12 log fac: 19.9872 approx : 19.9872  error : -1.60434e-06 1/ error : -623310
 13 log fac: 22.5522 approx : 22.5522  error : -1.26222e-06 1/ error : -792254
 14 log fac: 25.1912 approx : 25.1912  error : -1.01084e-06 1/ error : -989277
 15 log fac: 27.8993 approx : 27.8993  error : -8.22004e-07 1/ error : -1.21654e+06
 16 log fac: 30.6719 approx : 30.6719  error : -6.77414e-07 1/ error : -1.4762e+06
 17 log fac: 33.5051 approx : 33.5051  error : -5.64836e-07 1/ error : -1.77043e+06
 18 log fac: 36.3954 approx : 36.3954  error : -4.7588e-07 1/ error : -2.10137e+06
 19 log fac: 39.3399 approx : 39.3399  error : -4.04663e-07 1/ error : -2.47119e+06
 20 log fac: 42.3356 approx : 42.3356  error : -3.46975e-07 1/ error : -2.88205e+06
 21 log fac: 45.3801 approx : 45.3801  error : -2.9975e-07 1/ error : -3.33612e+06
 22 log fac: 48.4712 approx : 48.4712  error : -2.60719e-07 1/ error : -3.83554e+06
 23 log fac: 51.6067 approx : 51.6067  error : -2.28181e-07 1/ error : -4.38248e+06
 24 log fac: 54.7847 approx : 54.7847  error : -2.00839e-07 1/ error : -4.97911e+06
 25 log fac: 58.0036 approx : 58.0036  error : -1.77697e-07 1/ error : -5.62757e+06
 26 log fac: 61.2617 approx : 61.2617  error : -1.57977e-07 1/ error : -6.33003e+06
 27 log fac: 64.5575 approx : 64.5575  error : -1.4107e-07 1/ error : -7.08865e+06
 28 log fac: 67.8897 approx : 67.8897  error : -1.26493e-07 1/ error : -7.9056e+06
 29 log fac: 71.257 approx : 71.257  error : -1.13856e-07 1/ error : -8.78302e+06
 30 log fac: 74.6582 approx : 74.6582  error : -1.02848e-07 1/ error : -9.72308e+06
 31 log fac: 78.0922 approx : 78.0922  error : -9.32145e-08 1/ error : -1.07279e+07
 32 log fac: 81.558 approx : 81.558  error : -8.47474e-08 1/ error : -1.17998e+07
 33 log fac: 85.0545 approx : 85.0545  error : -7.72755e-08 1/ error : -1.29407e+07

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=