2
$\begingroup$

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;
            }
    }
}
$\endgroup$
8
$\begingroup$

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

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.