On Mon, Feb 5, 2018 at 11:44 AM, Stefan Beller <sbel...@google.com> wrote: >>> Having a stringlist of potentially new dirs sounds like the algorithm is >>> at least n^2, but how do I know? I'll read on. >> >> Yes, I suppose it's technically n^2, but n is expected to be O(1). >> While one can trivially construct a case making n arbitrarily large, >> statistically for real world repositories, I expected the mode of n to >> be 1 and the mean to be less than 2. My original idea was to use a >> hash for possible_new_dirs, but since hashes are so painful in C and n >> should be very small anyway, I didn't bother. If anyone can find an >> example of a real world open source repository (linux, webkit, git, >> etc.) with a merge where n is greater than about 10, I'll be >> surprised. >> >> Does that address your concern, or does it sound like I'm kicking the >> can down the road? If it's the latter, we can switch it out. > > I think that is fine for now; the real world usage matters more > than the big O notation. But maybe you want to hint at the possibility of > speedup (in the commit message or in code?), once someone produces > a slow case and digs up the code.
Sounds like a good idea; I'll add a comment about this issue to the commit message.
