4 ms·
>> Snowpack is a O(1) build system… Every file goes through a linear input -> build -> output build pipeline > Seems like O(n) to me? Big O notation describes
by pimterry 6y ago
>> Snowpack is a O(1) build system… Every file goes through a linear input -> build -> output build pipeline
> Seems like O(n) to me?
Big O notation describes how for a given operation (sorting a list), a given measurement (e.g. items compared, memory used, CPU cycles) grows in relation to a set of variables describing the input to the operation (number of elements).
Here their operation is 'a single-file incremental compilation', they're measuring how many files need recompiling in total, and the only variable n is 'the number of files in the project'.
In that case, Snowpack is O(1), and most other bundlers are O(n). They're not wrong.
You can argue that that's not an interesting point, or that there's other measurements that matter more ofc. It's not wrong though, and imo incremental single-file changes are a thing you care about here, and only ever processing one file in doing so is an interesting distinction between Snowpack and other bundlers.
Big O notation is not (ever) defining any detail of the operation in terms of every possible conflating variable. All Big O comparisons include implicit definitions: the exact same sorting algorithm could be described as both O(nlogn) for item comparisons required per n items in the list, or O(kn^2) for memory copies required per k bytes of largest item & n items, and both are accurate & useful descriptions.
(Sorry to be pedantic, but there's a _lot_ of replies here that have misunderstood big O entirely)