CODEWITHSUNDEEP
c++performancetime-complexity
Will
Will

Reputation: 3

Big O Complexity of this double loop

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.

Upvotes: 0

Views: 115

Answers (2)

selbie
selbie

Reputation: 104524

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²

Upvotes: 3

Giriteja Bille
Giriteja Bille

Reputation: 166

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)

Upvotes: 0

Related Questions