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?

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
– GriffeyDog, Commented Oct 27, 2020 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
– Paul Hankin, Commented Oct 27, 2020 at 16:27
@VLAZ How is O(n * log n) better than any linear algorithm? — fps
– fps, Commented Oct 27, 2020 at 16:27
@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
– fps, Commented Oct 27, 2020 at 16:30
@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
– John Kugelman, Commented Oct 27, 2020 at 16:36

Esotopo21 · Accepted Answer · 2020-10-27 16:31:34Z

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.

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related