1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Ben Steffan Jul 1 '17 at 13:21
  • \$\begingroup\$ Yes, i did wanted to know its Bachmann–Landau notation. Well, thank you for updating me about it. \$\endgroup\$ – Firoz Memon Jul 1 '17 at 13:30
3
\$\begingroup\$

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.]

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Firoz Memon Jul 1 '17 at 13:34
  • \$\begingroup\$ @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. \$\endgroup\$ – Ben Steffan Jul 1 '17 at 13:36
  • \$\begingroup\$ What do you mean by "Java makes no guarantees about the time and space complexity of methods" ? \$\endgroup\$ – Simon Forsberg Jul 1 '17 at 14:08
  • 1
    \$\begingroup\$ @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). \$\endgroup\$ – Ben Steffan Jul 1 '17 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.