Does using size() function of string inside a recursive function results in large delay/complexity?

Question

I was implementing different versions of a recursive function that checks whether a string is a palindrome and calculating complexities for them, but was confused about passing the string size as a parameter or calculating it using size() function and store it in a variable created inside the function, which would be more efficient?

Here's an Example of the 2 versions of the function:

bool isPalindrome1 (string s) {
    int sz = s.size();            // size calculated and stored
    if (sz < 2) return true;
    return ((s[0] == s[sz-1]) && isPalindrome1(s.substr(1, sz-2)));
}

and,

bool isPalindrome2 (string s, int sz) {    //size passed as parameter
    if (sz < 2) return true;
    return ((s[0] == s[sz-1]) && isPalindrome2(s.substr(1, sz-2), sz-2));
}

The first function would obviously take more time "time needed for size() function to return the size" but would this be of a significant delay if the original string size was kinda large? how's the complexity here calculated?

Note: I know this isn't the most efficient way to check recursively if a string is a palindrome, I'm just trying to better understand complexity and recursion.

*but would this be of a significant delay if the original string size was kinda large?* -- No, a string knows its size. There is nothing to calculate or count. — PaulMcKenzie, Jan 11 '19 at 01:29
..in contrast to strlen and a “C NUL-terminated string”.. — user2864740, Jan 11 '19 at 01:43
The `substr` isn't cheap. If you're worried about efficiency I'd get rid of that too. — Retired Ninja, Jan 11 '19 at 02:25
You're passign the string by value, that will slow you down. — Mark Ransom, Jan 11 '19 at 02:25

score 2 · Accepted Answer · answered Jan 11 '19 at 02:07

Since C++11, std::string::size() has constant complexity. Before that, its complexity was recommended to ("should") be constant, and I know of no compilers that would not follow this recommendation.

In practice, the string size value is either already stored in the string object or calculated as a difference between two stored pointers.

Does using size() function of string inside a recursive function results in large delay/complexity?

1 Answers1