3 ms·
> It seems that the complexity is O(N^2) rather than O(2*N^2) as I expected. This is interesting! Obviously, my understanding of LINQ was incorrect. Perhaps ju
by karmakaze 3y ago
> It seems that the complexity is O(N^2) rather than O(2*N^2) as I expected. This is interesting! Obviously, my understanding of LINQ was incorrect.
Perhaps just a wording problem, but big-O notation doesn't care about constant factors.
- klysm 3y agoNot only does it not care, it’s literally by definition that those two are identical
- klysm 3y agoIn practice though the factor of two can be relevant
- beart 3y agoThe author explicitly stated O(2*N^2) is the same as O(N^2), but maybe that was a later edit?
- karmakaze 3y agoYeah it's edited, but still miscommunicating--this section should drop the big-O if it want to talk about constant factors.
- nemetroid 3y agoWhat the author means is that they thought that the complexity was O(n^2) for two different reasons, but it turned out that only one of those reasons was valid. But abusing big-O notation is not a good way to express that.