Two approaches to count occurrences of one char in a String in Java

Question

I have two approaches:

First Approach:

int count =0;
for(int i = 0; i < text.length(); i++) {
 if(text.charAt(i) == charToCheck){
 count++;
 }
}
System.out.println(count);

Second Approach:

count = text.length() - text.replaceAll(
 String.valueOf(charToCheck),"")
 .length();
System.out.println(count);

Which one is fast w.r.t Time & Space Complexity? Why?

Are there any more approaches (which I am not aware of)? If yes, Please let me know.

• Ben Steffan: What do you mean by Time & Space Complexity? If it's Landau notation you seek, the first one is obviously O(n) for time and O(1) for space. The second one is probably O(n) time and O(n) space (because a second String is constructed, which, on worst case, has n chars), but this depends on the implementation of replaceAll.
• Firoz Memon: Yes, i did wanted to know its Bachmann–Landau notation. Well, thank you for updating me about it.

Answer 1

As I stated in the comments, both of your approaches have a time complexity of O(n), but your first approach has a O(1) space complexity whilst your second one requires O(n) space in the worst case, because replaceAll creates a copy with all the matches removed.

From complexity point of view, your first approach is basically ideal. In order to replace all occurrences of a char, you at least have to iterate every char in your input once, which corresponds to O(n) time complexity. Also, space complexity is, as stated, O(1) which is, obviously, the best case.

---

[Note: Java makes no guarantees about the time and space complexity of methods. Thus, replaceAll could, in theory, also have a much worse time and space complexity if not implemented well. I assumed that it runs in O(n) (which is the best case) when matching on a single char only. This fact, of course, makes the second approach even worse.]

• Firoz Memon: Are there any other approaches for reducing the time complexity? If yes, please update me. If no, still update me. I'll mark your answer accepted and close this thread. Thanks.
• Ben Steffan: @FirozMemon As I said, no. You cannot achieve anything below O(n), because you always need to look at each char at least once. If you have n chars, that's n operations, which means O(n) is the theoretical minimum. I advise you to refresh your knowledge on Landau notation.
• Simon Forsberg: What do you mean by "Java makes no guarantees about the time and space complexity of methods" ?
• Ben Steffan: @SimonForsberg As far as I'm aware, there is no official document which describes what time complexities conforming implementations of the standard library have to have, unlike, for example, c++. Thus, the complexity could vary from implementation to implementation (such as OpenJDK vs. OracleJDK).