What is the time complexity of String compareTo function in Java?

Question

I have a String array String strs[] = {"flower", "flow", "flight"};.

I want to find the smallest and largest lexicographically string from the array. This is what I did:

String first = strs[0], last = strs[0];

for (String str : strs) {
    if (str.compareTo(first) < 0)
        first = str;
    if (str.compareTo(last) > 0)
        last = str;
}

System.out.println("First : " + first + " Last : " + last);

Now I want find the time complexity of this algorithm. I know it will be n * (time complexity of compareTo()). So, what is the time complexity of this algorithm?

It's hardly going to be sub-linear. From pure complexity perspective, a good sorting algorithm will give you `O(n * log n)`, so it's on average better to sort and get the first and last element. — VLAZ, Oct 27 '20 at 16:15
If the strings are typically going to be different and unordered, the complexity is going to be closer to O(1) than O(n) for compareTo. — GriffeyDog, Oct 27 '20 at 16:24
The worst case is O(S) where S is the length of the strings. If you have n strings all of length S, the worst case of your algorithm is O(nS). As GriffeyDog partially points out, if you know something about the distribution of your strings, the average case may be much better. — Paul Hankin, Oct 27 '20 at 16:27
@VLAZ How is `O(n * log n)` better than any linear algorithm? — fps, Oct 27 '20 at 16:27
Related question: [String comparison time complexity](https://stackoverflow.com/questions/37419578/string-comparison-time-complexity) — geocodezip, Oct 27 '20 at 16:28
@fps because a linear algoruthm is *for the comparison*. Running `O(n)` over a collection is going to be compound. — VLAZ, Oct 27 '20 at 16:28
@VLAZ Sorry, but I fail to see how and why sorting and then picking the first and last elements is better than traversing the whole array (which is `O(n)`) to find the min and max elements — fps, Oct 27 '20 at 16:30
@VLAZ a sorting algorithm performs O(n log n) string comparisons, but this question is asking about time complexity of character comparisons. — Paul Hankin, Oct 27 '20 at 16:31
@fps `O(n) * O(m)` - you're not taking into account either traversing the collection or comparing the strings. — VLAZ, Oct 27 '20 at 16:33
@VLAZ You're making the same mistake. Sorting would be O(S*n log n) where S is the average length of the strings. A single pass linear scan is unquestionably better than sorting. — John Kugelman, Oct 27 '20 at 16:36

score 3 · Accepted Answer · answered Oct 27 '20 at 16:31

public int compareTo(String anotherString) {
    int len1 = value.length;
    int len2 = anotherString.value.length;
    int lim = Math.min(len1, len2);
    char v1[] = value;
    char v2[] = anotherString.value;

    int k = 0;
    while (k < lim) {
        char c1 = v1[k];
        char c2 = v2[k];
        if (c1 != c2) {
            return c1 - c2;
        }
        k++;
    }
    return len1 - len2;
}

This is the implementation of String#compareTo which leads to consider the complexity, in the worst case scenario (len1 = len2 = n), as O(n)

So the complexity of your algorithm would be O(nm) with n = number of strings in your array and m the max length among those strings lenghts.

What is the time complexity of String compareTo function in Java?

1 Answers1