CODEWITHSUNDEEP
c++algorithmtime-complexitybig-o
csguy
csguy

Reputation: 1474

If the only input is a String and an additional String is created, is the function O(n) space complexity?

For example:

    string longestPalStartingAtIndex(string s, int index) {
        int i = index - 1; 
        int j = index + 1;
        
        while (j < s.size() && s.at(index) == s.at(j)) j++;
        
        while (i >= 0 && j < s.size()) {
            if (s.at(i) == s.at(j)) {
                i--; j++;
            }
            else {break;}
        }

        return s.substr(i + 1, (j - 1) - (i + 1) + 1);
        
    }

    string longestPalindrome(string s) {
        
        string longest; string temp;
        for (int i = 0; i < s.size(); i++) {
            temp = longestPalStartingAtIndex(s, i);
            if (longest.size() < temp.size()) longest = temp;
        }
        return longest;
        
    }

In longestPalindrome, since n is the string s or the length of it, is creating an additional string (meant to store some substring of s) going to make the function O(n) space complexity?

Upvotes: 0

Views: 36

Answers (1)

Bill Lynch
Bill Lynch

Reputation: 81986

Yes. You're correct. The code you've shown has O(s.size()) space complexity.

Arguably the function calls to longestPalStartingAtIndex will also copy s and require space, but in the end we're talking about O(some_constant * s.size()) so it is still O(s.size()).

Upvotes: 1

Related Questions