Search code examples
javatime-complexityguavacomplexity-theory

time complexity: google.common.base.Joiner vs String concatenation


I know that using += on strings in loops takes O(n^2) time where n is the number of loops. But if the loop will run at most 20 times. Will that change the time complexity to O(1) ? For example,

List<String> strList = new ArrayList<>();
//some operations to add string to strList
for(String str : strList) appendStr += str + ","; 

I know that the size of strList will never exceed 20. Also each string in strList will have less than 20 characters. If the string concatenation in this case still has O(n^2) time complexity, would it better be to use google.common.base.Joiner if I want my algorithm to have a better time complexity?


Solution

  • In a very pedantic sense yes, if your input is capped at a fixed size than any operations performed on that input are effectively constant-time, however that misses the purpose of such analysis. Examine how your code behaves in the asymptotic case if you are interested in its time complexity, not how it behaves for a single specific input.

    Even if you cap the size of the list to 20 elements, you're still doing O(n^2) "work" in order to concatenate the elements. Contrast that with using a StringBuilder or higher-level tool such as Joiner which are designed to be more efficient than repeated concatenations. Joiner only has to do O(n) "work" in order to construct the string you need.

    Put simply, there's never a reason to do:

     for(String str : strList) appendStr += str + ","; 
    

    instead of:

    Joiner.on(',').join(strList);