>> 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.
