Testing PRNG w/ Chi-Squared & Kolmogorov-Smirnov Tests

[anachin6000]

I was developing a physical RNG and I was trying to test it using The Chi-Squared test and The Kolmogorov-Smirnov Test. The latter gives me some problems.
I have an attached photo with a table. In the table, n is the number of generated numbers. The book says that the test should be run for n=1000. I've made a program that calculates the K parameters and I should compare them with values from the table. There is no set of values for n=1000, but there is a formula in the table to continue to calculate values.
In the formula, there is a -O(1/n) that troubles me. I reversed the formula to get -O(1/n) from the data in the table, but it makes no sense.

 

[mfb]

The values from the formula are wrong by something that is probably of the order of 0.001. Mathematically O(1/n) doesn't guarantee that, but it won't be significantly larger.
You can probably ignore it, or include it as conservative estimate in the direction that hurts you.

 

[Khashishi]

Big O notation is used to indicate that a formula or equation is just an approximation, and the O(x) tells you an asymptotic bound on the size of the error in the approximation. Usually, you see this when the approximation is some kind of series expansion for a transcendental function, and the series has been cut off at some point.
e.g.
$exp(x) = 1 + x + x^2/2 + O(x^3)$
This approximation is valid for |x| << 1. When |x| < 1, higher powers like $x^4, x^5$ are smaller than $x^3$. So, we say the error bound is O(x^3) and absorb all the smaller higher order terms into the largest error. The big O notation ignores constant coefficients because we don't care about that level of detail when working with asymptotic behavior. Really, we are only interested something even coarser than an order of magnitude.

For x > 1, it isn't correct to absorb terms like x^4, x^5, ... into the error of the x^3 term since these higher terms get bigger, not smaller. It doesn't make sense to do a series approximation in terms of increasing powers. But for some functions, you can do a series approximation in terms of decreasing powers (1/x, 1/x^2, 1/x^3 ...). In this case, you can write something like f(x) = g(x) + c/x + O(1/x^2).
All the higher terms get absorbed into O(1/x^2).

It sounds kind of wishy washy, but there is a rigorous formality to it.

 

[Khashishi]

Big O notation is also used in computer science to talk about the time or memory used by an algorithm as we scale the problem size. Basically, we want algorithms that scale well, like O(n) or O(n log n), and not like O(2^n) which is basically means we will never be able to use this algorithm for a large size of n, no matter how fast our computers get.