# Longest Palindrome Brute Force

I'm confused by the running time of the following algorithm. I've been told it's $O(n^3)$, but there are only two loops. How can that be?

for(int i = 0; i < s.length(); ++i) {
for(int j = i; j <= s.length(); ++j) {
String sub = s.substring(i, j);
if(isPalindrome(sub) && sub.length() > maxCount) {
maxCount = sub.length();
longestP = sub;
}
}
}


There's a loop hidden inside isPalindrome(). Possibly also one inside substring() and/or length(), depending on how they're implemented.

You can't just count loops. When we say that an algorithm runs in time $O(n^3)$, we mean that it takes "at most roughly" $n^3$ basic steps. You need to check whether the steps of the algorithm really are basic, or whether they also involve iterations through data structures. "Basic" corresponds to something like "taking a fixed number of machine instructions, regardless of the input" but this is an informal analysis, so I'm not going to try to give a formal definition.

There's also the technicality that any algorithm that runs in, say, exactly $n^2$ steps runs in time $O(n^3)$, time $O(n^4)$, time $O(2^{2^n})$ and so on, since the definition of $O(\cdot)$ involves an "at most".

• Of course! Thank you so much. That's exactly it. The loop within isPalindrome. – Question Feb 15 '17 at 20:35

isPalindrome function kinda looks like:

bool isPalindrome(std::string str){
int len = str.length();
int low = 0, high = len - 1;
while(high > low){
if(str[low++] != str[high--])
return false;
}
return true;
}


So for each i and j steps, the function would run another n times based on the size of input, thus leave us with a time complexity of O(n^3).

• Welcome to CS@SE. What insight does this provide in addition to David Richerby's answer? – greybeard Dec 8 '19 at 9:00
• @greybeard its gives a pretty good insight as to the time complexity is hiding under the hood – handlerFive Dec 17 '19 at 10:39