Hacker News Reader

Comment by dandelany | Hacker News Reader

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

View on HN

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 since we are talking pedantry pedantic is, er, spelt pedantic not peedantic. Sorry I couldn't resist!

Reply on news.ycombinator.com