Calculate the time complexity of this specific algorithm

Question

public static String findLongestSubstring(String str) {
for (int len = str.length(); len >= 2; len--) {
    for (int i = 0; i <= str.length() - len; i++) {
        String substr = str.substring(i, i + len);
        int vowels = countVowels(substr);
        int consonants = len - vowels;
        if (vowels == consonants) {
            return substr;
        }
    }
}
return "";
}

private static int countVowels(String str) {
return str.replaceAll("[^AEIOUaeiou]+", "").length(); 
 }

From:problem

MY CALCULATION:

The first loop has (str.length - 1) rotations. The second loop depends on the first loop, so it goes like: (0), [0, 1], [0, 1, 2] , ... , [0, 1 .., str.length - 2] Thus this is a total of (Second loop only) 1 + 2 + ... + N - 2 = (2N-3)^2/8 -1/8 ~ (2N)^2. If we let N=str.length. In the first loop, we have (N-1) ~ N, thus a total of ~N^3. But then we have to assume that inside both the loops, it is O(1) otherwise we have have > O(N^3)?

But I don't think this is right.

How do we calculate such a time complexity?

The outer loop has a complextiy of O(n) because it depends on the string length. The inner loop also depends on the string length (in the worst case) and thus it has O(n) complexity too. The body of the inner loop also depends on the string length although that's not that obvious (the string operations need to iterate over all characters) and thus it too has O(n) complexity. Now you do `outer * inner * body`, i.e. O(n) * O(n) * O(n), and thus get O(n^3). — Thomas, Sep 21 '16 at 15:39
@JonnyHenly since constant values don't matter in big-O notation it would be reduced to `n * n`. But your calculation probably doesn't take the complexity of the inner loop's body into account. — Thomas, Sep 21 '16 at 15:41
@Thomas, How does the inner loop iterate from 1->n-1? If it goes from 1->1 then 1->2 then 1->3 ,.... 1->n-1, shouldn't it be the sum 1 + 2 + 3 + ... + (n-1)? — YOGIYO, Sep 21 '16 at 16:16
@YOGIYO you're basically right but when determining the complexity of an algorithm you consider the worst case and ignore any constant factors. Thus the inner loop still depends on the string length resulting in O(n) complexity. Please also see Andreas' answer. — Thomas, Sep 22 '16 at 08:37

Davide Lorenzo MARINO · Answer 1 · 2016-09-21T15:44:44.547

2

If n is the length of str.

The external loop can be approximated (as you did) to O(n).

The inner loop can be approximated to O(n) too, because it goes from a minimum of 0 cycles to a maximum of n cyles when length is 0.

So if you DON'T consider what happens internally in substring and replaceAll methods the complexity is O(n) * O(n) -> O(n^2).

Note that the replaceAll iterate over the whole string, so his internal complexity is O(n). Considering also this the complexity is O(n^3).

edited Sep 21 '16 at 15:44

answered Sep 21 '16 at 15:39

Davide Lorenzo MARINO

26,420
4
39
56

How does the inner loop iterate from 1->n-1? If it goes from 1->1 then 1->2 then 1->3 ,.... 1->n-1, shouldn't it be the sum 1 + 2 + 3 + ... + (n-1)? – YOGIYO Sep 21 '16 at 16:16

score 2 · Accepted Answer · edited May 23 '17 at 12:15

2

Assuming n is length of str, you get:

Outer loop iterates n - 1 times: O(n)
Inner loop iterates 1 to n - 1 times, so on average n / 2 times: O(n)
replaceAll() inside countVowels() iterates over 2 to n characters, so on average n / 2 + 1 times: O(n)
Total is O(n) * O(n) * O(n), so: O(n³)

^{Note: Performance of substring() depends on version of Java, so it is either O(1) (earlier Java) or O(n) (later Java). But since O(1) + O(n) and O(n) + O(n) is both O(n), it makes no difference for performance of inner loop body, which is why the above logic only considers the performance of replaceAll().}

UPDATE

There are three ways of calculating performance for outer and inner loop combined, excluding what happens in the body:

O math: Outer loop is O(n), and inner loop is O(n), so total is O(n) * O(n) = O(n²)
Iteration math: Outer loop iterates n - 1 times, and inner loop iterates n / 2 times (on average), so total is (n - 1) * (n / 2) = n² / 2 - n / 2. Since only fastest growing factor counts, that means O(n²)
Iteration sum: Sum the iterations of inner loop, i.e. 1 + 2 + ... + n-1. Sum of a sequence can be calculated as count * average, and average can be calculated as (min + max) / 2. That means that average = (1 + n-1) / 2 = n / 2, and sum = (n - 1) * (n / 2), which is exactly the same result we got in #2 above, so it is O(n²)

As you can see, O math was simpler, so that's why it was chosen for the answer.

edited May 23 '17 at 12:15

Community

1
1

answered Sep 21 '16 at 15:42

Andreas

154,647
11
152
247

How does the inner loop iterate from 1->n-1? If it goes from 1->1 then 1->2 then 1->3 ,.... 1->n-1, shouldn't it be the sum 1 + 2 + 3 + ... + (n-1)? – YOGIYO Sep 21 '16 at 16:16
@YOGIYO It does when you sum across the iterations of the outer loop. That sequence has `n-1` numbers, so the sum can be calculated as `count * average`, which means `(n-1) * (1+n-1)/2 = (n-1)*n/2` which is _O(n²)_. Same result you get when you consider the two loops independently, and get _O(n)_ * _O(n)_, which is also _O(n²)_. In the above answer, the second bullet considers the performance of a *single* run of the loop itself, which is why you then have to multiply by the outer loop to get the total. – Andreas Sep 21 '16 at 16:54
I have one question, I'd be grateful if you answered this. For the second loop we have `for(int u=0; u – YOGIYO Sep 22 '16 at 01:21
@YOGIYO I'm not considering `len=2` anywhere. Not for the outer loop, or the inner loop, or the loop body. You seem to overlook that I'm talking about the **average**. And on *average*, the inner loop will iterate `n / 2` times *for each* time it is invoked by the outer loop. Which means that in *total*, it iterates `(n - 1) * (n / 2)` times, which means _O(n²)_. – Andreas Sep 22 '16 at 01:58
If I could I'd give you another upvote for the update. :) – Thomas Sep 22 '16 at 08:42
I get it now, so you take that at any point in the second loop on average it runs n/2 times and then multiply * (n-1) for the times the outer loop runs! Thanks a lot. Now I am going to try to calculate the inner loop – YOGIYO Sep 22 '16 at 12:24

Calculate the time complexity of this specific algorithm

2 Answers2