An incremental rebuild will still be O(n), but in this case n=1. This isn't the same as O(1) where, regardless of the input size, the number of operations will remain the same. This isn't just being pedantic, O(1) implies they have a seperate algorithm that doesn't grow as input size grows, which is totally seperate from intelligently running an algorithm whose runtime increases at a constant rate. While in this case the resulting runtime will be the same, the nuances that are implicitly implied when they say something is O(1) will not be true.
Surely that depends on what you call `n`, they are using `n` to refer to the number of files in the project.
I would agree that the term is a bit of "shorthand" that doesn't perfectly map to the idea of big-O complexity - for exactly the reason you mention, build time still depends on the size of the file. But for me, it was shorthand that helped me understand the idea. They had two other options on how to write this - either leave out the big-O stuff entirely, or explain it more deeply eg. "most bundlers are O(lmn) where l is the number of files, m is the number of files changed, n is the number of JS tokens per file" or something. Both of these options may have been more "technically correct" but would've taken me longer to grok the idea than the way they have it written. Maybe they should just have a footnote for the pedants explaining that O(1) is more of an idiom than a technical claim in this case :P
Yes, exactly. O(n) means that as n (the number of files in the projects) grows, so does the runtime complexity. O(1) means that as n grows, the runtime complexity remains constant. In this case, they're always using an input of size n=1, but this doesn't make the algorithm itself O(1). By calling this an O(1) operation, they imply that you could rebuild your entire project at the same rate you can rebuild a project with just one file changed. This is misleading and untrue, which is why it's not peedantic.
It wouldn't be a problem if it wasn't on a technical page like this where this distinction can have large implications (such as the one above). When I read that it was O(1) I drew conclusions that were both very favorable to snowpack and also completly untrue. It'd be like if you said you drove a truck but you actually drove an accord. It's probably fine to say that 99% of the time, but it could cause issues if you say it to your mechanic because they'll conclude things from what you said that might not be accurate.
If you have a project with 1000 files in it, how often are you editing all 1000 of them at the same time? Virtually never from my experience.
The way they've structured "rebuilds" is to only "build" (or really probably do very little if anything) to just that one file you edited and saved.
Yes if you edit all 1000 files it's going to take longer.
"In theory there's no difference between theory and practice. In practice, there is." I think this is one of those cases where in practice it's awfully close to O(1) so while they're technically incorrect practically it's difficult to tell the difference.
This esp. compared with something like Angular in which you're looking at many, many seconds of build time to get started. I think it's laudable.
> If you have a project with 1000 files in it, how often are you editing all 1000 of them at the same time? Virtually never from my experience.
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.
> 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).
It's only misleading if you take it out of context and examine that one sentence without reading the rest of the article. It's perfectly clear what they mean in the post (to me, at least).
> An incremental rebuild will still be O(n), but in this case n=1.
TFA explains pretty clearly what claim is being made. They're talking about the cost of rebuilding one file, given the "input" of a project with n files. They claim that for other build systems that cost (the cost of one file) scales linearly with total project size, but for theirs it doesn't.
Your objection here redefines n to be the number of files changed, but they don't claim anything about that.
They didn't claim anything about the cost of changing multiple files. "Rebuild one file, in a project of size n" is the operation they're examining the performance of.
There is such a thing as best-case, worst-case, and average-case computational complexity.
Also in this case complexity we seem to care about is function of two factors: number of files and number of changed files. Call the first one n and the second one p.
The complexity of webpack would be O(n) + O(p) [+] and the complexity of snowpack would be O(p) in development. Worst case p = n, but best case p = 1, and usually in development p is on average very close to 1. Also p is parallelisable, making it appear like p = 1 WRT wall clock time for small p values even though CPU time would be O(p).
[+]: which one of the p or n constant factors dominates is unclear, but some hardly parallelizable n-bound processing is always present for webpack.
