On Mon, Apr 27, 2015 at 4:06 PM, Tab Atkins Jr. <jackalm...@gmail.com> wrote: > On Mon, Apr 27, 2015 at 3:42 PM, Ryosuke Niwa <rn...@apple.com> wrote: >>> On Apr 27, 2015, at 3:15 PM, Steve Orvell <sorv...@google.com> wrote: >>> IMO, the appeal of this proposal is that it's a small change to the current >>> spec and avoids changing user expectations about the state of the dom and >>> can explain the two declarative proposals for distribution. >>> >>>> It seems like with this API, we’d have to make O(n^k) calls where n is the >>>> number of distribution candidates and k is the number of insertion points, >>>> and that’s bad. Or am I misunderstanding your design? >>> >>> I think you've understood the proposed design. As you noted, the cost is >>> actually O(n*k). In our use cases, k is generally very small. >> >> I don't think we want to introduce O(nk) algorithm. Pretty much every >> browser optimization we implement these days are removing O(n^2) algorithms >> in the favor of O(n) algorithms. Hard-baking O(nk) behavior is bad because >> we can't even theoretically optimize it away. > > You're aware, obviously, that O(n^2) is a far different beast than > O(nk). If k is generally small, which it is, O(nk) is basically just > O(n) with a constant factor applied.
To make it clear: I'm not trying to troll Ryosuke here. He argued that we don't want to add new O(n^2) algorithms if we can help it, and that we prefer O(n). (Uncontroversial.) He then further said that an O(nk) algorithm is sufficiently close to O(n^2) that he'd similarly like to avoid it. I'm trying to reiterate/expand on Steve's message here, that the k value in question is usually very small, relative to the value of n, so in practice this O(nk) is more similar to O(n) than O(n^2), and Ryosuke's aversion to new O(n^2) algorithms may be mistargeted here. ~TJ
