CODEWITHSUNDEEP
c++algorithmcomplexity-theorybig-o
Itai Sagi
Itai Sagi

Reputation: 5615

Calculating the big-O complexity of this string match function?

can anyone help me calculate the complexity of the following?
I've written a strStr function for homework, and although it's not part of my homework, I want to figure out the complexity of it.

basically it takes a string, finds 1st occurence of substring, returns it's index,
I believe it O(n), because although it's double loop'd at most it'll run only n times, where n is the length of s1, am I correct?

int strStr( char s1[] , char s2[] ){
    int haystackInd, needleInd;
    bool found = false;
    needleInd = haystackInd = 0;

    while ((s1[haystackInd] != '\0') && (!found)){
        while ( (s1[haystackInd] == s2[needleInd]) && (s2[needleInd] != '\0') ){
            needleInd++;
            haystackInd++;
        }
        if (s2[needleInd] == '\0'){
            found = true;
        }else{
            if (needleInd != 0){
                needleInd = 0;

            }
            else{
                haystackInd++;
            }
        }
    }

    if (found){
        return haystackInd - needleInd;
    }
    else{
        return -1;
    }
}

Upvotes: 1

Views: 2360

Answers (3)

C--
C--

Reputation: 123

Your algorithm isn't correct. The indices, haystackInd, in your solution are incorrect. But your conclusion based on your wrong algorithm was right. It is O(n), but just it can't find the first occurrence of the substring. The most trivial solution is like yours, compare string S2 to substrings starting from S1[0], S1[1],...And the running time is O(n^2). If you want O(n) one, you should check out KMP algorithm as templatetypedef mentioned above.

Upvotes: 0

user1130005
user1130005

Reputation: 412

It is indeed O(n), but it is also not functioning properly. Consider finding "nand" in "nanand"

There is an O(n) solution to the problem though.

Upvotes: 3

Scott Hunter
Scott Hunter

Reputation: 49896

Actually, the outer loop could run 2n times (each iteration increments haystackInd at least once OR it sets needleInd to 0, but never sets needleInd to 0 in 2 successive iterations), but you end up w/ the same O(n) complexity.

Upvotes: 2

Related Questions