What is the big O complexity of the following java algorithm? The algorithm is u

Question

What is the big O complexity of the following java algorithm?

The algorithm is used to take a String s of uppercase letters and break them into substrings of English words. I'm a bit confused about the complexity, though. My initial thought was O(n2) since the second for loop must check the dictionary for each substring to see if it is in the dictionary, but i've also heard that each call to str.substring(0, i) before the recursive portion may also constitute another n checks. If that is the case, the complexity would be O(n3).

Can someone help me analyze this algorithm for it's complexity? Thanks.

Explanation / Answer

The Java-7's 6th update onwards, the substring function has started to create a copy of the said substring. So this takes O(n). Making the complexity of the algorithm in question to be O(n3).

Earlier to that, Java did the substring operation without making a copy, so it took O(1). Making the complexity of the algorithm in question to be O(n2).

It just happens that you are correct either way.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.