3 ms·
>Seems like O(n) to me? As the number of files grows, so does the speed of your builds? O(n) effectively approximates O(1) with sufficiently low values of n
by aphextron 6y ago
>Seems like O(n) to me? As the number of files grows, so does the speed of your builds?
O(n) effectively approximates O(1) with sufficiently low values of n
- deleted 6y ago[deleted]
- adtac 6y agoIf we're just going to make up new definitions for existing terminology, why even bother discussing anything?
- XCSme 6y agoI think you confused some definitions, what you are saying sometimes applies for O(constant), for example you can consider O(57) to be O(1), if the number "57" never changes even though the input size changes. O(n) by defition means that execution time grows lineary with input size.
- tylerhou 6y agoYou 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_algorithm https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a...