Big O Complexity of this double loop

Question

I have been trying to figure out the Big O Complexity of this code:

void findSection(string s)
{
    string start = "abc";
    string end = "xyz";

    int startIndex = s.find(start);
    string tempS;
    while(startIndex<s.size())
    {
        for(int i=startIndex; i<=s.size()-3; i+=3)
        {
            tempS = s.substr(i,3);
            if(tempS==end)
            {
                return;
            }
        }
        startIndex = s.find(start,startIndex+3);
    }
}

Worse case would be if:

s="abcabcabcabc.......

Orignally I though the complexity would be O(nlog(n)), but after looking at this link: Time Complexity of this double loop

I came up with the complexity as:

i=0 ——>   0,3,6,9,…,b   b
i=3 ——>   3,6,9,…,b     b-3
i=6 ——>   6,9,…,b       b-6
i=9 ——>   9,…,b         b-9
i=b ——>                 b-b

b + (b-3) + (b-6) + ... + (b-b) = _____

And now I am thinking it might be O(n^2) but I am not sure. Thank you for your time and help.

Time complexity of inner loop will be O(logn) whenever (i = i * constant) after every iteration. In the current scenario you are incrementing i by 3 but worst time complexity of inner loop isn't effected by addition of constant. It will remain O(n). — Talal02, May 03 '21 at 05:49

selbie · Accepted Answer · 2021-05-03T05:47:33.503

3

TDLR: O(N²)

Outer loop is N iterations (one iteration for each char in the string).

Inner loop:

A normal inner loop that starts on the index of the outer loop is N/2. But since it's incremented by 3, It's (N/2)*(1/3). Or simply N/6

N*(N/6) is N²/6. Hence order of the highest polynomial: N²

edited May 03 '21 at 05:47

answered May 03 '21 at 05:41

selbie

100,020
15
103
173

score 0 · Answer 2 · answered May 03 '21 at 05:43

0

Big O Time complexity is O(N*N) as you are clearly going through the second loop where the program ends only when it iterates over divider of 3 times. To be precise , the time complexity is < O(N^2)

answered May 03 '21 at 05:43

Giriteja Bille

168
1
13

Big O Complexity of this double loop

2 Answers2