Longest Palindrome Brute Force

Question

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;
            }
    }
}

Answer 1

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".

Answer 2

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).