Big O Method Complexity

Question

I have this method:

public static int what(String str, char start, char end) { int count=0; for(int i=0;i<str.length(); i++) { if(str.charAt(i) == start) { for(int j=i+1;j<str.length(); j++) { if(str.charAt(j) == end) count++; } } } return count; } 

I need to find:

1) What is he doing? Answer: by counting the total number of final occurrences after the EACH (or is it? Not indicated in the task, point 3 depends on this) start.

2) What is its complexity? Answer: the first loops completely iterate over the entire line, so it is at least O (n), the second loop is executed only if the start char is found and even partially (the index from which the start + 1 was found). Although, big O is all about the worst case? Therefore, in the worst case, start is the first char, and the internal iteration of the iteration along the line is n-1 times, -1 is a constant, so n. But the inner loop will not be performed statistically at each outer iteration pass, but since large O is the worst case, is it right to say that its complexity is O (n ^ 2) ? Ignoring any constants and the fact that in 99.99% of cases the inner loop will not execute every pass of the outer loop.

3) Rewrite it so that complexity is lower.
I’m not sure that the start is started no more than once or more, if not more, then the method can be rewritten using one cycle (with a flag indicating whether the start was started and whence the number of samples increased at each end occurrence), which gives complexity O (n) .

In case this launch may appear several times, that most likely it is because the destination has a Java course, and I don’t think they will make such an ambiguity.
The solution in this case is not possible using a single loop ... WAIT ! Yes this..!
It is just necessary that the variable, say, inc, increase every time it starts up and be used to increase the counter every time each end of the time occurs after the first start is detected:

 inc = 0, count = 0 if (current char == start) inc++ if (inc > 0 && current char == end) count += inc 

Will this also lead to O (n) complexity? Because there is only 1 cycle.

Yes, I understand that I wrote a lot of hehe, but I also realized that I understand much better, forming my thoughts into words ...

Answer 1

• It increments the counter for each trailing character after any run. Therefore, if there is more than one start, it can increase it more than once for the same end.
• In the worst case, it will call charAt (n ^ 2 - n) / 2 = ((n - 1) + (n - 2) + ... + 1) times. This is O (n ^ 2). This happens when every character starts.
• If you counted the trailing characters after the first run, you can simply return the score after the internal one. But since the number of times the score increases depends on the number of starts, your final pseudo code is on the right track. However, you need to switch the order of ifs to deal with a special case, where start == end. You also don't need to check if inc> 0.

 inc = 0, count = 0 if (current char == end) count += inc if (current char == start) inc++ 

This is O (n) in all cases.

Answer 2

1) Yes. 2) Yes, the complexity at best is O (n) and at worst O (n ^ 2).
3) Almost right. You need to check the end character before the start character, otherwise the result is not always correct. Example in C #:

 public static int what(string str, char start, char end) { int count = 0, mul = 0; foreach (char c in str) { if (c == end) count += mul; if (c == start) mul++; } return count; } 

Answer 3

• As Matthew already pointed out, the complexity of the original method is O (n ² )
• Your second approach is wrong, the original method seems to count all the substrings starting with start and ending with end , which can also contain either start or end .
• This can be done in O (n), just find all the starts, all the ends, and then iterate over two lists, moving the pointers accordingly.