On Saturday, April 21, 2012 18:26:42 H. S. Teoh wrote: > Actually, I don't think the nested loops affect Big-O complexity at all. > The O(l) complexity (where l = string length) is already inherent in the > string comparison "str < otherStr". Adding more loops over the strings > doesn't change the Big-O complexity (you just make O(l) into 3*O(l) > which is the same as O(l)).
If the loop is really nested, then it will increase the Big(O) complexity, whereas if it's parallel to a similar loop, it will just increase the constant factor. Which it really is in this case, I don't know without sitting down and sketching out the exact algorithm, but certainly upon a first glance, it was my conclusion that the loops were nested. If they're not, then they're not. Regardless of whether it's the Big(O) complexity or the constant factor that's the problem here, clearly there's enough additional overhead that it's causing problems for Jay's particular case. It's also the sort of thing that can be easy to miss and then end up wondering why your code is so slow (if it actually matters in your particular situation). - Jonathan M Davis