Re:Snowpack 2.0
by tylerhou on Thursday May 28, 2020 @05:52AM
(#23335433)
You have a misunderstanding of O notation.
When we say O(n), we say that as n goes towards to infinity, the runtime grows as k * n, where k is some constant.
Your sentence effectively says:
> (k * n runtime as n approaches infinity) effectively approximates (j runtime as n approaches infinity) for sufficiently low values of n.
This makes no sense, because you can't have n approach infinity and also be a "sufficiently low value" at the same time.
I think what you were trying to say is that O(n) algorithms run in constant time (or "fast enough") given a constant input size. But in that case, O notation is meaningless because when we use it, we specifically care about what happens at infinity.
Also, O(1) isn't synonymous with "fast enough"; constant factors can matter a lot. For example, the "fastest" (Big O wise) matrix multiply algorithm has such a large constant factor that using it is not feasible for matrices that fit on today's computers. https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a...
When we say O(n), we say that as n goes towards to infinity, the runtime grows as k * n, where k is some constant.
Your sentence effectively says:
> (k * n runtime as n approaches infinity) effectively approximates (j runtime as n approaches infinity) for sufficiently low values of n.
This makes no sense, because you can't have n approach infinity and also be a "sufficiently low value" at the same time.
I think what you were trying to say is that O(n) algorithms run in constant time (or "fast enough") given a constant input size. But in that case, O notation is meaningless because when we use it, we specifically care about what happens at infinity.
Also, O(1) isn't synonymous with "fast enough"; constant factors can matter a lot. For example, the "fastest" (Big O wise) matrix multiply algorithm has such a large constant factor that using it is not feasible for matrices that fit on today's computers. https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a...