Comment by strombofulous | Hacker News Reader

Comment by strombofulous | Hacker News Reader

Parent Full thread

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