Re:Snowpack 2.0
by spinningslate on Thursday May 28, 2020 @08:29AM
(#23336450)
> They could say that other build systems are O(n) where n is the total number of files, while this one is O(n) where n is the number of modified files. It's immediately clear then how this is better for the build use-case, while still making it clear how the efficient it is as the input size grows.
That's a great, concise and clear articulation. The project would do well to quote you on that!
If anyone's still struggling with the difference between O(1) and O(n), there's a common example with lists that might help:
1. Getting the head of a list is usually O(1). It doesn't matter how long the list is, getting the head element always takes the same amount of time.
2. Getting the length of a list is usually O(n). The time taken to count the list entries grows in proportion with the length of the list.
As an aside, note also that a list with a single entry doesn't make the length function O(1).
For the purposes of Big-O notation, this does not matter. If they didn't need its semantics, they should not have used the notation. Simple as that.
It's still O(n), regardless of the fact that they have optimized constants and in the best case it may be less than that. Irrelevant. Big O establishes an upper bound. Bubble sort is still bubble sort, we don't care if it is quick when you are ordering two elements.
Maybe they meant to advertise Ω(1) on the best case, and compared to other build systems?
EDIT: another poster says that "n" refers to the number of files in the project. Still misleading. Usually we are interested in how the complexity grows as the number of inputs grow. Big O purposely discards constants.
They could say that other build systems are O(n) where n is the total number of files, while this one is O(n) where n is the number of modified files. It's immediately clear then how this is better for the build use-case, while still making it clear how the efficient it is as the input size grows.